赤裸裸的0-1背包，很水。聽說省賽要出DP題，我們隊(duì)三個(gè)人都不擅長DP，于是乎我開始從背包問題入手學(xué)習(xí)動(dòng)態(tài)規(guī)劃?？戳藥滋斓谋嘲?，頭都大了，還是不理解，今天終于A掉了一道水題，值得紀(jì)念一下。
關(guān)于背包這里就不多說了，感興趣的童鞋可以參考《背包問題九講》。
#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
小鼠標(biāo) 閱讀(228)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
DP