又是一道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
*/