背包问题综合

1. 01背包
   问题：若干个物体，每个价值为c[i]重量为w[i]，数量均为1，背包最大容量为W，问怎样取物体才能最大化收益？
   解法：dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值。有递推关系式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])。这里的第一维度可以省略。
   注意这里的内存重量循环j为W到0，递减关系（保证每个物体取一遍）（后面的不会修改前面的）
   当背包空间j少于当前物体的重量时不选该物体这一步可以省略，对后续没有影响。
   最终写法为：
   

   1  for(int i=1; i<=m; i++) //物品 
   2         for(int j=W; j>=0; j--) //容量 
   3         {
   4             if(j >= w[i])
   5                 dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);
   6             else      //只是为了好理解
   7                 dp[i][j] = dp[i-1][j];           
   8         }

    

2. 完全背包
   问题：若干个物体，每个价值为c[i]重量为w[i]，数量均为无限，背包最大容量为W，问怎样取物体才能最大化收益？
   解法：dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值。有递推关系式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])。这里的第一维度可以省略。
   注意这里的内存重量循环j为w[i]到W，递增关系（保证每个物体取一遍）（后面的不会修改前面的）
   最终写法为：
   

   1  for(int i=1; i<=n; i++)
   2         for(int j=w[i]; j<=W; j++)//注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
   3             f[j]=max(f[j],f[j-w[i]]+c[i]);

   
   例题：POJ2229
   题意：
   找一些2^x(0<=x)，使它们的和为N。比如，N=7： 
   1) 1+1+1+1+1+1+1 
   2) 1+1+1+1+1+2 
   3) 1+1+1+2+2 
   4) 1+1+1+4 
   5) 1+2+2+2 
   6) 1+2+4 
   (1 <= N <= 1,000,000). 
   解法：直接完全背包即可，注意关系式更新的时候为“拿”的情况加上“不拿”的情况；注意初始化dp[0]=1

    1 int N;
    2 int num[25];
    3 int dp[1000000 + 5];
    4 int main() {
    5     // freopen("input.txt", "r", stdin);
    6     scanf("%d", &N);
    7     num[1] = 1;
    8     dp[0] = 1;
    9     for (int i = 2; i <= 25; i++) num[i] = num[i - 1] * 2;
   10     for (int i = 1; i <= 21; i++) {
   11         for (int j = num[i]; j <= N; j++) {
   12             dp[j] = (dp[j] + dp[j - num[i]]) % MOD;
   13         }
   14     }
   15     printf("%d\n", dp[N]);
   16     return 0;
   17 }

    

背包问题综合

原文：https://www.cnblogs.com/romaLzhih/p/11415141.html