hdu3466 Proud Merchants 变形的0-1背包

   这道题看了解题报告后才懂的，第一次遇到这种变形的背包，不过真是很难想到要先按照Q-P排序。。。
 
下面说一下我对本题的理解。
 
     首先讲一下暴力解决，很显然我们可以用枚举的方法，对每个物品都有选与不选两种决策。但即使暴力也存在一个问题，比如对 3 5 6，5 10 5这两个物品，如果我们的决策是两个都不选或者是只选其中一个，显然没什么问题，但如果我们要是两个都选的话，按照之前这个顺序有m>=13，但如果把两个的顺序交换一下则m>=10即可，从这里就可以看出问题的所在了。于是，对任意两个物品i，j，为了避免上面存在的那种问题，我们可以算出两种顺序所需要的最少金额，若i->j，则至少需要Pi+Qj,若是j->i则至少需要Pj+Qi。如果已知结果是i->j较优的话，则有Pi+Qj<Pj+Qi，即Qi-Pi>Qj-Pj。所以若对之前的物品先按照Q-P由大到小排好序后，然后暴力就可以解决了。但这种暴力其实已有较好的算法可以解决了，即0-1背包，说到这里原问题就已经完全转化为了普通的0-1背包了
 
    但还有一点需要要解释一下，刚才是说暴力是按照Q-P从大到小先排好序，但由于dp与暴力其实正好是两个逆过程，dp的好处就不再多解释了，即避免对子问题的重复计算。所以dp前我们是按照Q-P从小到大的顺序排好序。
 
OK，此题总算完满解决了!
 
[cpp]  
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
  
using namespace std;  
struct goods  
{  
    int p,q,v,d;  
    bool operator<(const goods t)const  
    {  
        return d<t.d;  
    }  
}g[501];  
int dp[5001];  
  
int main()  
{  
    int n,m,i,j;  
    while(~scanf("%d%d",&n,&m))  
    {  
        memset(dp,0,sizeof(dp));  
        for(i=1;i<=n;i++)  
        {  
            scanf("%d%d%d",&g[i].p,&g[i].q,&g[i].v);  
            g[i].d=g[i].q-g[i].p;  
        }  
        sort(g+1,g+n+1);  
        for(i=1;i<=n;i++)  
            for(j=m;j>=g[i].q;j--)  
                dp[j]=max(dp[j],dp[j-g[i].p]+g[i].v);  
        printf("%d\n",dp[m]);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,