HDU 3466 Proud Merchants
【摘要】 题目链接~~>
做题感悟：这题想到排序，但是没排对。
解题思路：这个题目增加了变量q 因此就不能简单是使用01背包了。
证明：因为如果一个物品是5 9，一个物品是5 6，对第一个进行背包的时候只有dp[9],dp[10],…,dp[m]，
再对第二个进行背包的时候，如果是普通的，应该会借用前面的d...
做题感悟：这题想到排序，但是没排对。
解题思路：这个题目增加了变量q 因此就不能简单是使用01背包了。
证明：因为如果一个物品是5 9，一个物品是5 6，对第一个进行背包的时候只有dp[9],dp[10],…,dp[m]，
再对第二个进行背包的时候，如果是普通的，应该会借用前面的dp[8],dp[7]之类的但是现在这些值都是0，所以会导致结果出错。于是要想到只有后面要用的值前面都可以得到，那么才不会出错。设A:p1,q1 B:p2,q2，如果先A后B，则需满足 Vj-p2>=q1 (1) 才能使背包B时不受A的影响因为要比较dp[j]与dp[j-p2] 如果dp[j-p2]未更新的话 就会得出错误的结论了同时也有 Vj-p1>=q2 不成立即 Vj-p1<=q2 (2) (因为B不在A前面) ps：等于是不管谁在前都不会受影响由(1)、(2)得 q1-p1<=q2-p2 时 A在B前面 背包B时不会受前面A的影响.
代码：
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
const double PI = 3.1415926 ;
-
const int INF = 99999999 ;
-
const int MX =100005 ;
-
int dp[MX] ;
-
struct node
-
{
-
int v,u,w ;
-
}T[MX] ;
-
bool cmp(node a,node b)
-
{
-
return a.u-a.v < b.u-b.v ;
-
}
-
int main()
-
{
-
int n,m ;
-
while(~scanf("%d%d",&n,&m))
-
{
-
for(int i=0 ;i<n ;i++)
-
scanf("%d%d%d",&T[i].v,&T[i].u,&T[i].w) ;
-
sort(T,T+n,cmp) ;
-
memset(dp,0,sizeof(dp)) ;
-
for(int i=0 ;i<n ;i++)
-
for(int j=m ;j>=T[i].u ;j--)
-
if(dp[j]<dp[j-T[i].v]+T[i].w)
-
dp[j]=dp[j-T[i].v]+T[i].w ;
-
printf("%d\n",dp[m]) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/21401579
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）