不多說了，最赤裸的01背包問題。
01背包壓縮的動態方程為f[v]=Max(f[v],f[v-Ci]+Wi)。
詳情參閱《背包九講》：
http://wenku.baidu.com/view/519124da5022aaea998f0f22.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20000
#define LENN 4000
typedef struct
{
int w;
int d;
}Charm;
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j;
Charm cm[LENN];
int N, M;
int f[LEN];
while(scanf("%d%d", &N, &M) != EOF)
{
for(i = 1; i <= N; i++)
scanf("%d%d", &cm[i].w, &cm[i].d);
memset(f, 0, sizeof(f));
for(i = 1; i <= N; i++)
for(j = M; j >= cm[i].w; j--)
f[j] = Max(f[j], f[j - cm[i].w] + cm[i].d);
printf("%d\n", f[M]);
}
//system("pause");
}
posted on 2012-08-14 10:44
小鼠標 閱讀(366)
評論(0) 編輯 收藏 引用 所屬分類:
DP