hdu 3466 Proud Merchants 自豪的商人（01背包，微变形）

题意:

　　要买一些东西，每件东西有价格和价值，但是买得到的前提是身上的钱要比该东西价格多出一定的量，否则不卖。给出身上的钱和所有东西的3个属性，求最大总价值。

思路：

　　1）WA思路：与01背包差不多，dp过程中记录每个容量所能获得的最大价值以及剩余的容量。实现是，开个二维dp数组，从左往右扫，考虑背包容量为j的可获得价值量，根据该剩余容量得知要更新后面哪个背包容量[j+?] ，如果剩余容量大于q[i]那么可以直接装进去，更新价值以及剩余容量，否则，考虑更新的是更大的背包容量。这个思路有缺陷，一直找不到。

　　2）AC思路：先看代码，下面再证明其正确性。

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 struct node

 {

     int p,q,v;

 } a[];

 int cmp(node x,node y)//按q-p排序，保证差额最小为最优

 {

     return x.q-x.p<y.q-y.p;

 }

 int main()

 {

     int n,m,i,j;

     int dp[];

     while(~scanf("%d%d",&n,&m))

     {

         for(i = ; i<n; i++)

             scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);

         memset(dp,,sizeof(dp));

         sort(a,a+n,cmp);//关键：q-p 小的在前

         for(i = ; i<n; i++)

         {

             for(j = m; j>=a[i].q; j--)//注意：剩余的钱大于q才能买

             {

                 dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);

             }

         }

         printf("%d\n",dp[m]);

     }

     return ;

 }

别人的AC代码

证明：

假设有物品1~n，

1）考虑第1件物品：j 的范围在m~q[1]，因为有钱q[1]是能买到物品1的最低前提，那么对dp[m~q[1]]进行更新，结果都是v[1]，而dp[0~q[1]]都是0（不包括dp[q[1]]）。是正确的。

2）考虑第2件物品：因为状态转移公式是 dp[j] = max(dp[j], dp[j-p[i]] + v[i])，所以疑虑在于式子j-p[2]>=q[2]-p[2]是否成立。根据第2个for的限制条件，可知 j-q[2]>=0，两边各减去p[2]，那么j-p[2]>=q[2]-p[2]，以上式子成立。可知：j-p[1]是能够满足第2件物品的差额要求的。

3）考虑第i件物品，由于1~i-1这些物品都满足限制条件才会购买，那么第i件物品同样和第2件物品一样的证明。

巴特西

hdu 3466 Proud Merchants 自豪的商人（01背包，微变形）

最新文章

热门文章