做题感悟:这题想到排序,但是没排对。
解题思路:这个题目增加了变量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的影响.
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 ; }