HDU3466 01背包

  大概意思是給你2個數分別代表物品個數和你帶的錢數，每個物品有3個值，p,q,v，分別表示買該物品所花的錢，買該物品最低所帶的錢，物品的價值。得出最大的價值。

很明顯是01背包。

則狀態轉移方程為:
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].w).

若保證動歸方程無後效性，dp[j-a[i].p]一定要比dp[j]先算，j最小為a[i].q，所以需按q-p從小到大排序。

代碼如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct mem{
 8     int p, q, w;
 9 }a[550];
10 
11 bool cmp(mem a,mem b)
12 {
13     return a.q-a.p<b.q-b.p;
14 }
15 
16 main()
17 {
18     int n, m, dp[5005], i, j, k;
19     while(scanf("%d%d",&n,&m)==2)
20     {
21         for(i=0;i<n;i++)
22     scanf("%d %d %d",&a[i].p,&a[i].q,&a[i].w);
23     sort(a,a+n,cmp);
24     memset(dp,-1,sizeof(dp));
25     for(i=0;i<n;i++)
26     {
27         for(j=m;j>=a[i].q;j--)
28         dp[j]=max(dp[j],dp[j-a[i].p]+a[i].w);
29     }
30     printf("%d\n",dp[m]+1);
31     }
32     
33 }