POJ 2642 Charm Bracelet

题解：01背包的入门题 不知道为什么二维数组RE了 所以一维滚动数组可以A掉

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[13000];
int cost[13000],rating[13000];
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<=m;i++)
        dp[i]=0;
        for(int i=1;i<=n;i++)
        cin>>cost[i]>>rating[i];
        for(int i=1;i<=n;i++)
            for(int j=m;j>=cost[i];j--)
            dp[j]=max(dp[j],dp[j-cost[i]]+rating[i]);
        cout<<dp[m]<<endl;
    }
    return 0;
}