标准的01背包
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_N 3405
int w[MAX_N],d[MAX_N];
int dp[12881];
int main()
{
int n,m;
cin>>n>>m;
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>w[i]>>d[i];
for(int i=0;i<n;i++)
{
for(int j=m;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
}
}
cout<<dp[m]<<endl;
}poj 3624 Charm Bracelet,布布扣,bubuko.com
原文：http://blog.csdn.net/iweberxie/article/details/23944221