3466 ACM Proud Merchants 变形的01背包

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3466

题意：假设你有M元，已经Pi，Qi，Vi（i为角标，1<i<N),当M>Qi,时才能购买该商品，得到价值Vi，问得到的最大的价值。

思路：知道是变形的01背包问题，但是思考了很久不知道怎么解决，于是看了好几种不同款式的大佬的代码和证明才看懂，如下是自己写的证明：

如果不改变，直接用01背包的话呢，就是：

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

for(int j=v;j>=a[i].Q,j--）

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

这个dp使用前是没有对商品排序的，就是商品的购买顺序本该对他没影响，但是在本题中购买a->b,和购买b->a,是不一样的，

假设有两组数据：

2 M

a:P1,Q1,V1

b:P2,Q2,V2

a->b  需要的背包容量：P1+Q2

b->a  需要的背包容量：P2+Q1

自然我们需要剩下背包的容量更大的方案进行购买，及如果a->b,就有：P1+Q2<P2+Q1 移项为 Q1-P1>Q2-P2，也就是说我们每次选择时都希望购买 Q-P更大的商品；

但是对应我们的dp：

for(i = 0;i<n;i++)
for(j = m;j>=a[i].Q;j--)
dp[j] = max(dp[j],dp[j-a[i].P]+a[i].v);

实质是：当满足j>=a[i].Q时，就马上确定购买物品i，然后再用剩下的j-a[i].P去购买最大价值，i的购买顺序是先于j-a[i].P的，所以dp的顺序就希望从Q-P小的先dp，

于是用sort排序，由于默认是升序，但是本题中：

sort(a,a+n）会出错，因为有a.p,a.Q.a.v,a.ca,多个a,会不知道是哪一个a作为首地址，a+n作为尾地址。

于是先写下：

bool cmp(note A,note B)
{
return A.ca < B.ca;
}

再

sort(a,a+n,cmp)

就知道是a.ca了

代码：

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int dp[5010];

struct note
{
int P,Q,v;
int ca;
} a[510];
bool cmp(note A,note B)
{
return A.ca < B.ca;
}

int main()
{
int n,m,i,j;
while(~scanf("%d%d",&n,&m))
{
for(i = 0;i<n;i++)
{
scanf("%d%d%d",&a[i].P,&a[i].Q,&a[i].v);
a[i].ca = a[i].Q-a[i].P;
}
sort(a,a+n,cmp);
memset(dp,0,sizeof(dp));
for(i = 0;i<n;i++)
for(j = m;j>=a[i].Q;j--)
dp[j] = max(dp[j],dp[j-a[i].P]+a[i].v);
printf("%d\n",dp[m]);
}
}

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有