hdu3466 Proud Merchants

标签：01背包

/*    题意：N件物品，每件3个属性：P(价格)，Q()，V(价值)。          Q：想买这件物品，手中至少有钱Q。虽然你只要花费钱P，但若不足Q，不能买。          有钱M，最多能获得多少价值的东西。    解：按(Q - P)的大小，把物品从小到大排序，然后01背包，dp[m]就是结果。*/#include
   
    #include
    
     #include
     
      using namespace std;const int maxn = 5005;int dp[maxn];struct note{    int P,Q,V;    int m;}item[505];bool cmp(note A, note B){    return A.m < B.m;}int main(){    int N, M;    while(scanf("%d %d", &N, &M) != EOF)    {        for(int i = 0; i < N; i++)        {            scanf("%d %d %d", &item[i].P, &item[i].Q, &item[i].V);            item[i].m = item[i].Q - item[i].P;        }        sort(item, item + N, cmp);  ///        memset(dp, 0, sizeof(dp));  //ZeroOnePack template        for(int i = 0; i < N; i++)            for(int j = M; j >= item[i].Q; j--)  ///                dp[j] = max(dp[j], dp[j - item[i].P] + item[i].V);        printf("%d\n", dp[M]);    }    return 0;}

分析:
一。为什么要按照(Q-P)排序。
我们先想这么一个问题:给你n个这种商品，你最少需要多少钱能够买下来。(通过这个问题，可以找出一个性质。) 把这个商品转化一下：还是有三个属性P(价格)、V(价值)、M(Q-P)。
Sum = P1 +P2 +P3 +…+Pn+max(Mi-(P(i+1)+P(i+2)+………..Pn))。
要使得Sum 最小,就应该按照M从大到小排序,然后求解。
也就是说我们应该先买M最大的物体,然后买M第二大的…最后M买最小的。这个性质是这个问题的关键。

二。用DP中01背包的思想实现。
dp[j] = max(dp[j], dp[j - volume[i]] + value[i]); (j为第j个物品。这是用一维数组实现的01背包。)
dp[j - volume[i]]是指,我们在容量为j的包中放了volume[i]之后,还能放的物品的价值。
i从1到n, dp[j - volume[n]]是放了第n个物品后,还能放多少价值的物品。所以这里volume[n]的M值应该最大。
通俗的说：这个dp过程正好是逆向的。dp[j - volume[i]]是dp[j]的最优子结构。
所以,在DP的时候,我们应该按照M的值从小到大排序。
也就是说,我们应该按照(Q-P)的值,从小到大排序再DP。

欢迎指出文中的bug,十分感谢！