不多说了，最赤裸的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
小鼠标 阅读(332)
评论(0) 编辑 收藏 引用 所属分类:
DP