背包问题 HDU3466 Proud Merchants
Proud Merchants
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 6633 Accepted Submission(s): 2769
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?
Input There are several test cases in the input.
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.
Output For each test case, output one integer, indicating maximum value iSea could get.
Sample Input 2 10 10 15 10 5 10 5 3 10 5 10 5 3 5 6 2 7 3 Sample Output 5 11 Author iSea @ WHU Source 2010 ACM-ICPC Multi-University Training Contest(3)——Host by WHU Recommend zhouzeyong | We have carefully selected several similar problems for you: 3460 3463 3468 3467 3465 题解来自sdfzchy,为什么不自己写题解呢?之前屯题一直没有更博客,等到想更的时候才发现……真烦…… 题目大意:n个商品,m元钱,每种商品都有p,q,v,p价格,q表示买这种商品你需要带q元老板才愿意和你交易,v这种商品的实际价值。求问最多可以获得多少价值
题解: 01背包的变形;
假设有2个物品,A(P1,Q1,V1),B(P2,Q2,V2)。
如果先买A后买B需要(不等于花费)P1+Q2,如果先买B后买A需要P2+Q1,选择两者之中较小的能保证遍历所有情况。
若先买A,则P1+Q2 < P2+Q1 ,即Q2-P2 < Q1-P1。故应先买q-p较大的
考虑0/1背包中的更新其实是逆向的,所以要把q-p从小到大排序,再做01背包。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 int n,m; 7 int f[50010]; 8 struct dt{ 9 int p,q,v; 10 bool operator<(const dt&aa)const{ 11 return q-p aa.p; 12 } 13 }data[510]; 14 int main(){ 15 while(scanf("%d%d",&n,&m)!=EOF){ 16 memset(f,0,sizeof(f)); 17 for(int i=1;i<=n;i++) scanf("%d%d%d",&data[i].p,&data[i].q,&data[i].v); 18 sort(data+1,data+n+1); 19 for(int i=1;i<=n;i++) 20 for(int j=m;j>=max(data[i].q,data[i].p);j--) 21 f[j]=max(f[j],f[j-data[i].p]+data[i].v); 22 printf("%d\n",f[m]); 23 } 24 return 0; 25 }