又是一道01背包裸题。
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX(a,b) a>b?a:b
using namespace std;
const int MAXN = 1000005;
int dp[MAXN];
int w[MAXN];
int val[MAXN];
int n,m;
int main()
{
while(scanf("%d%d",&n,&m)){
for(int i=0;i<n;i++){
scanf("%d%d",&w[i],&val[i]);
}
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
for(int j=m;j>=w[i];j--){
dp[j] = MAX(dp[j],dp[j-w[i]]+val[i]);
}
}
printf("%d\n",dp[m]);
}
return 0;
}
/*
[来源] POJ 3624
[题目] Charm Bracelet
[大意]
01背包模板题。
[输入]
4 6
1 4
2 6
3 12
2 7
[输出]
23
*/