赤裸裸的0-1背包，很水。听说省赛要出DP题，我们队三个人都不擅长DP，于是乎我开始从背包问题入手学习动态规划。看了几天的背包，头都大了，还是不理解，今天终于A掉了一道水题，值得纪念一下。
关于背包这里就不多说了，感兴趣的童鞋可以参考《背包问题九讲》。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 14000
int N, M;
int W[LEN];
int D[LEN];
int f[LEN];
int max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
void bag()
{
int i, j;
for(i = 0; i <= N; i++)
f[i] = 0;
for(i = 1; i <= N; i++)
for(j = M; j >= W[i]; j--)
f[j] = max(f[j], f[j - W[i]] + D[i]);
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i = 1; i <= N; i++)
{
scanf("%d%d", &W[i], &D[i]);
}
bag();
printf("%d\n", f[M]);
//system("pause");
}
posted on 2012-05-08 09:47
小鼠标 阅读(221)
评论(0) 编辑 收藏 引用 所属分类:
DP