POJ 3624 Charm Bracelet

01背包问题，使用常规二维dp数组会Memory Limit Exceeded。
因此使用1维dp数组，从后往前遍历。(建议先理解理解常规二维dp数组，再思考本题)
dp 背包问题模板链接

题目链接POJ 3624

题目大意

背包问题，给你背包体积M及N个物品。给出物品体积和价值，求背包最大价值。
但由于体积和物品数过大，所有无法开出二维数组。但dp[i][j]中遍历第i个商品这个操作其实是可以隐含起来的。对于第X个商品，需要比较dp[x-1][j]与dp[x-1][j-X.w]+X.d，就是只需要通过前一行的某个小体积的dp数组值来更新得到新状态，因此我们可以从大体积往小体积遍历，将结果直接存在dp数组中。简单来说，就是将dp[i][j]中的i行全部合在一行了。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
struct charm
{
        int w,d;
}a[3410];
int cmp(charm a,charm b)
{
        if(a.w==b.w)
        {
                return a.d>b.d;
        }
        return a.w<b.w;
}
int dp[13000];//dp[j]表示体积为j时最大价值，但注意这里省略了dp[i][j]中的i。
int main()
{
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i].w>>a[i].d;
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
                for(int j=m;j>=0;j--)
                {
                        if(j>=a[i].w&&dp[j-a[i].w]+a[i].d>dp[j])
                        {
                                dp[j]=dp[j-a[i].w]+a[i].d;
                        }
                }
        }
        cout<<dp[m]<<endl;
        return 0;
}