HDU 5410 CRB and His Birthday（完全背包变形）

CRB and His Birthday

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 430 Accepted Submission(s): 237

Problem Description

Today is CRB's birthday. His mom decided to buy many presents for her lovely son.
She went to the nearest shop with

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output the maximum candies she can gain.

Sample Input

Sample Output

21
Hint

CRB's mom buys 10 presents of first kind, and receives 2 × 10 + 1 = 21 candies.

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

Recommend

wange2014 | We have carefully selected several similar problems for you: 5416 5415 5414 5413 5412

大致三种方法：

1. 01背包+完全背包

先跑一遍01背包，价值为a+b的，然后再按价值为a的完全背包跑。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<string>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 2005
 8 #define M 12
 9 
10 int n,m;
11 int f[N],w[N],a[N],b[N];
12 
13 int main()
14 {
15     int T;cin>>T;
16     while(T--)
17     {
18         scanf("%d%d",&m,&n);
19         for(int i=1;i<=n;i++)
20         scanf("%d%d%d",&w[i],&a[i],&b[i]);
21 
22         memset(f,0,sizeof(f));
23 
24         for(int i=1;i<=n;i++)
25         {
26             for(int j=m;j>=w[i];j--)
27             {
28                 f[j]=max(f[j],f[j-w[i]]+a[i]+b[i]);
29             }
30             for(int j=w[i];j<=m;j++)
31             {
32                 f[j]=max(f[j],f[j-w[i]]+a[i]);
33             }
34 
35         }
36         cout<<f[m]<<endl;
37     }
38     return 0;
39 }

2. 完全背包的思路。每次有三种选择方案，1不选第i件物品，2选一个第2件物品，3选2个以上的第二件物品。

用一个辅助数组g记录上一行（上一个i）的最大糖果数的值，因为完全背包空间是从小到大的，所以同一个i后面的空间会用到前面的的值，这也就是完全背包的内涵，但是用了辅助数组g，记录上一行的状态，就保证使用a+b不会用到前面的值。

转移方程：f[j]=max3(f[j], f[j-w[i]]+a[i], g[j-w[i]]+a[i]+b[i]);

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<string>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 2005
 8 #define M 12
 9 
10 int n,m;
11 int w[N],a[N],b[N];
12 int f[N];//f[j]表示j元钱可以得到的最大糖果数
13 int g[N];//g[j]表示上一个i,j元可以得到的最大糖果数
14 
15 int max3(int a,int b,int c)
16 {
17     return max(a,max(b,c));
18 }
19 
20 int main()
21 {
22     int T;cin>>T;
23     while(T--)
24     {
25         scanf("%d%d",&m,&n);
26         for(int i=1;i<=n;i++)
27         scanf("%d%d%d",&w[i],&a[i],&b[i]);
28 
29         memset(f,0,sizeof(f));
30         memset(g,0,sizeof(g));
31 
32         for(int i=1;i<=n;i++)
33         {
34             for(int j=w[i];j<=m;j++)
35             {
36                 f[j]=max3(f[j], f[j-w[i]]+a[i], g[j-w[i]]+a[i]+b[i]);
37             }
38             for(int j=0;j<=m;j++)
39             {
40                 g[j]=f[j];
41             }
42         }
43         cout<<f[m]<<endl;
44     }
45     return 0;
46 }

3. 还是完全背包的思路，用dp[i][j][0]表示不取第i件物品，花费j得到的最大收益，dp[i][j][1]表示取第i件物品，花费j得到的最大收益，最终的结果就是max(dp[i][j][0],dp[i][j][1])。每次对于物品i，先得出不取它能得到的最大收益，然后再求取它能得到的最大收益。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 2005;
int dp[N][N][2];

int main ()
{
    int t;cin>>t;
    while ( t-- )
    {
        int m, n;
        scanf("%d%d", &m, &n);
        memset( dp, 0, sizeof(dp) );
        for ( int i = 1; i <= n; i++ )
        {
            int w, a, b;
            scanf("%d%d%d", &w, &a, &b);
            for ( int j = 0; j <= m; j++ )
            {
                dp[i][j][0] = max( dp[i-1][j][0], dp[i-1][j][1] );
            }
            for ( int j = w; j <= m; j++ )
            {
                dp[i][j][1] = max( dp[i][j - w][1] + a, dp[i][j - w][0] + a + b );
            }
        }
        printf("%d
", max( dp[n][m][0], dp[n][m][1] ));
    }
    return 0;
}

第一位空间可以压缩，把声明改成 int dp[N][2];最后结果改成max(dp[m][0],dp[m][1]).

中间关键代码换成

    for ( int j = 0; j <= m; j++ )
    {
        dp[i][j][0] = max( dp[i-1][j][0], dp[i-1][j][1] );
    }
    for ( int j = w; j <= m; j++ )
    {
        dp[i][j][1] = max( dp[i][j - w][1] + a, dp[i][j - w][0] + a + b );
    }