背包DP&整数划分模型（待更新……）

背包DP

• 0/1背包
• 完全背包
• 多重背包

一般是给出一些“物品”，每个物品具有一些价值参数和花费参数，要求 在满足花费限制下最大化价值或者方案数

0/1背包问题

给出 \(n\) 个物品，每个物品有 \(V_i\) 的价值和 \(W_i\) 的费用，我们总共有 \(m\) 块钱，求 最多能得到多少价值的物品

\(N<=10^3,m<=10^3\)

solution

每个物品只用了一遍

状态：

$ f[i][j]$ 表示前 \(i\) 个物品，用了 \(j\) 的花费得到的最大的价值

转移：

看第 \(i\) 个物品是否使用

\(f[i][j]=max(f[i-1][j] , f[i-1][j-w[i]]+v[i])\)

时间复杂度：

\(O(N*M)\)

   memset(dp,-0x3f,sizeof(dp));
   dp[0][0] = 0;
   for(int i = 1;i <= n; i++){
   	  for(int j = 0;j < w[i]; j++)f[i][j] = f[i - 1][j];
   	  for(int j = w[i];j <= m; j++)f[i][j] = max(f[i - 1][j],f[i - 1][j- w[i]] + v[i]);
   }

1.如果记录最大值方案数：

枚举的时候如果 \(f\) 值等于最大值，那就计数++，如果大于最大值就更新最大值

2.输出方案：

逆序思维倒着输出即可

滚动数组优化*

我们发现每组 \(f\) 更新的时候只和 \(i-1\) 有关，所以直接开一位数组转移即可

   memset(f,-0x3f,sizeof(dp));
   f[0] = 0;
    for (int i = 1;i <= n; i++){
      for (int j = m;j <= w[i]; j--)f[j] = max(f[j],f[j - w[i]] + v[i]);  
	}

为什么倒着枚举，废了我一晚上

为保证每个物品只能使用一次，我们倒序遍历所有 \(j\) 的值,保证在更新 \(f[j]\) 时候 \(f[j - w[i]]\) 不会被更新,这样保

证枚举背包空间的时候，都会用没有装这个物品的背包状态来转移；而如果正序枚举的时候， $ f[j - w[i]]$ 有可

能已经用这个物品更新过一次了，这样这个物品就会被反复用来两次，不符合规定

完全背包

每一类物品可以选无限个

solution

状态和01背包一个样

转移是关键

1 .如果不选：那么很明显 \(f[i][j] = f[i-1][j]\)

2 .如果选：先给个式子：

选的话，背包中应该至少出现一个这种物品，所以枚举到这个物品的时候因为 \(f[i][j - w[i]]\) 可能已经有了这个这种物品也可能没有，所以要再留出这个空间来存放这个物品，这个物品就有可能选多次

所以完全背包转移

node

   memset(dp,-0x3f,sizeof(dp));
   dp[0][0] = 0;
   for(int i = 1;i <= n; i++){
   	  for(int j = 0;j < w[i]; j++)f[i][j] = f[i - 1][j];
   	  for(int j = w[i];j <= m; j++)f[i][j] = max(f[i - 1][j],f[i][j- w[i]] + v[i]);
   }

01背包和完全背包区别（特别小）

01背包： \(f[i-1][j-w[i]]+v[i]\) 前一个空间已经是 \(j-w[i]\) 了，如果还买一个这个物品空间就满了，所以就只能买一次

完全背包：\(f[i][j-w[i]]+v[i]\) 当空间为 \(j-w[i]\) 可能已经买了这个物品，现在枚举到 \(i\) 时又留下这些空间来买这个物品，所以可以多件这个物品

优化：

根据上面的 01背包的保证每个物品只能选一个，所以倒叙枚举来避免选择同一个物品多次的情况，而现在正序枚举就好了

node

   memset(f,-0x3f,sizeof(dp));
   f[0] = 0;
    for (int i = 1;i <= n; i++){
      for (int j = w[i];j <= m; j--)f[j] = max(f[j],f[j - w[i]] + v[i]);  
	}

多重背包

对于每个物品可以买最多能用 \(t[i]\) 次

每个最多选 \(t[i]\) 次暴力转移就好了，再枚举每个物品选多少次

复杂度：\(O( N*M*t[i] )\)

注意：k枚举的时候不能超过背包的上限 \(k*w[i] <= j\)

node

memset(f,-0x3f,sizeof(f));
   f[0][0] = 0;
   for(int i = 1;i <= n; i++)
   	  for(int j = 0;j <= m; j++){
   	    f[i][j] = f[i-1][j];
   	    for(int k = 1 ;k <= c[i] && k*w[i] = j;k++)
   	      f[i][j] = max(f[i][j],f[i-1][j-w[i]*k] + k*v[i]);
  	  }

同理：

memset(dp,-0x3f,sizeof(dp));
   f[0] = 0;
   for(int i = 1;i <= n; i++)
   	  for(int j = m;j >= 0; j--){
   	    for(int k = 1 ;k <= c[i] && k*w[i] = j;k++)
   	      f[j] = max(f[j],f[j-w[i]*k] + k*v[i]);
  	  }

背包DP&整数划分模型（待更新……）

原文：https://www.cnblogs.com/Arielzz/p/14382574.html