周氏背包九讲
在讲dp问题之前 先了解一下什么是dp
它的核心是什么
我想最简单的方法应该是从递归和递推入手 逐渐引入到dp问题 再然后就慢慢学着直接用dp的思路(闫氏dp分析法)想问题
首先第一步
从递归递推到dp
以两道例题的形式来引入
题目1：跳台阶
一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示方案数。
数据范围
1≤n≤15
分析：
递归（dfs)
对于任意一个台阶级数 都可以分为由它-1级走一步到达 由它-2级走两步到达
比如 七级台阶可以分成6级台阶走一步 5级台阶走两步 然后再递归处理6级和5级的情况
由此生成这样一棵递归搜索树
最小状态 2级台阶有两种走法（0走两次1步 和 0走一次两步） 1级台阶只有一种走法（0走一步）
递归的解法就这样出来了
#include<bits/stdc++.h>
using namespace std;
int n;
int dfs(int x)
{
//1 2是不可再分的 所以直接返回
if(x==1)
return 1;
else if(x==2)
return 2;
//对于其他情况就可以一直拆解递归
else
return dfs(x-1)+dfs(x-2);
}
int main()
{
cin>>n;
int res=dfs(n);
cout<<res;
return 0;
}
记忆化搜索
然后也如上图所示
很多地方都做了没意义的重复操作
发现其实只需要算最左边的那条分支 可以得到6 5 4 3 的方法数 把它们记录下来的话 右边就不需要做那么多递归操作了
直接简化成了近logn的复杂度（整棵树变一条枝）
这就是记忆化搜索 用一个数组 记录一下每个节点的答案 再遇到相同节点时 直接取即可
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int mem[N];//新增记忆化数组
int n;
int dfs(int x)
{
//若已存过 就返回记录的结果
if(mem[x])
return mem[x];
int sum=0;
if(x==1)
sum = 1;
else if(x==2)
sum = 2;
else
sum=dfs(x-1)+dfs(x-2);
mem[x]=sum;
return sum;
}
int main()
{
cin>>n;
int res=dfs(n);
cout<<res;
return 0;
}
省去递 直接推
接下来还能怎么优化
可以发现我们得到答案只是归的时候得到 和递并没有关系
能否省略从上往下递的步骤 直接由下而上的推出答案
(先把一个一个小问题解决 再解决由他们状态得到的母问题）
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int dp[N];
int n;
int main()
{
cin>>n;
dp[1]=1,dp[2]=2;
//把dfs的归部分 状态转移 成这样的递推公式
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n];
return 0;
}
滚动空间
再优化的话就是空间上了
发现其实每一个后状态只需要它的前面一个状态和前面两个状态 其他的其实没必要存下来
那么 就可以用滚动数组的思路
因为这里已经是一维了 那么就可以优化成0维 用两个变量交替滚动覆盖
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
int a,b,fn;
a=1,b=2;
for(int i=1;i<=n;i++)
{
if(i==n)
cout<<a;
fn=a+b;
a=b,b=fn;
}
return 0;
}
这题 我们由递归优化到记忆化搜索优化到简单的dp(递推）再使用滚动数组优化
也不难发现 dp就是将递归的递过程优化掉 从下而上地分析出答案 在这个过程中 又利用了记忆化的方式 潜在地剪去了很多不必要的分支 （一直都在做 得出答案 又同时微妙的省去了不必要的操作 我想这就叫做动态规划吧 妙）
题目2：打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
分析
不能简单的分析成 间隔一个偷——只偷奇数或者只偷偶数
这个问题其实还可以偷1 然后23不偷 再偷4 即可以不止间隔一个
所以想着分奇偶排序取两端求平均比大小是不可行的
可以发现 对于每个房间 不外乎就是两种选择 偷与不偷
若偷1的话 下一个一定是先从3开始考虑 如果不偷1的话 下一个一定是先从2开始考虑
（往左表示不偷该点 往右表示偷该点）
可以发现如果往右走 就需要加上前者累积的金额
dfs
还是可以先用暴搜实现 每一个房间 不偷的话递归处理它的下一个房间 偷的话递归处理它的下下个房间 且加上当前房间的金额数
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int n,T;
int dfs(int x)
{
if(x>n)
return 0;
//不同处在于这里返回的是max而不是和
else
//如果该点不偷就往左走找临近的店 如果偷就往隔两个的店考虑 并加上当前累计值
return max(dfs(x+1),dfs(x+2)+home[x]);
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
int res=dfs(1);//从第一个店看 偷不偷
cout<<res<<endl;
}
return 0;
}
记忆化
然后就是用记忆化数组 省去一些不必要的分支
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int mem[N];//添加记忆化数组
int n,T;
int dfs(int x)
{
if (mem[x])
return mem[x];
int sum=0;
if(x>n)
sum=0;
else
sum= max(dfs(x+1),dfs(x+2)+home[x]);
mem[x]=sum;
return sum;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
memset(mem,0,sizeof mem);//记得这里重置记忆化数组
int res=dfs(1);
cout<<res;
}
return 0;
}
递推(简单dp)
再然后舍去递的过程 直接做归（也就是推） 即简单dp
如上图也可见 大的是在递归搜索树的树叶处
所以应该是从大到小递推 推到1的时候停止得出答案
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int f[N];
int n,T;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
memset(f,0,sizeof f);
//因为1是由2 3的状态（小的根据大的）得出的 所以n应该由大到小
for(int i=n;i>=1;i--)
{
f[i]=max(f[i+1],f[i+2]+home[i]);
}
cout<<f[1];
}
return 0;
}
到这里应该就已经有些感觉了吧
可以先简单理解成
递归加上记忆化搜索 反过来就差不多是dp
递推实际是简单的dp 不过要在这里学会滚动数组的空间优化
官话来说就是：
- **动态规划（DP）**是一种用来解决优化问题的方法，通过将问题分解为重叠的子问题，然后自底向上地解决这些子问题，最终组合成问题的解。DP既可以看作是递归的一种特殊情况（带有记忆化的递归），也可以通过递推实现。
- 记忆化搜索：是将递归与DP结合的一种技术，通过存储递归过程中已经计算过的结果，避免重复计算，从而优化性能。
- 递推与DP：递推是实现DP的一种方法，特别是当问题可以通过遍历所有状态来解决时。在DP中，递推通过迭代更新状态转移数组，逐步构建最终解。
有了前两道题的引入 现在尝试一下01背包
题目3：01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
分析
拿到这个问题的时候先会有一种想法：
把每个物品排一下序
因为有个体积v还有个价值w 那把w/v就是性价比
把它排个序 然后用类似贪心的思想去写（每次选性价比最高的）
咋一看很有道理 但其实是不对的 比如 n=2 v=5
（1）v=5 w=5 性价比:1
（2）v=3 w=4 性价比：4/3 貌似（2）的性价比更高 但实际答案应该是（1）
这其实就是一个全局最优和局部最优的问题 （与Dijkstra贪心局部最优和spfa的考虑全局最优是异曲同工的）
对于这种考虑大局的问题 要使用dp去写 用贪心的话就显得目光短浅了
不扯了 分析这题
老规矩 还是先暴力去写 然后想办法改成dp
暴搜：
不外乎就是对于每个物品 有选和不选两种方案
与前面不同的是 此时的节点存放的是背包剩余体积和价值
而边表示对于每个物品选与不选（往左不选往右选）
然后孩子结点就是执行选或不选操作后 背包的新状态
那么显而易见 使用dfs可以得到所有答案 其中就可以得到最优解
从第一个物品开始选 初始的剩余空间spv为m
对于每个物品有选和不选两种方案
当背包剩余空间不够时（spv<v[x]）只能不选
当背包剩余空间够时（spv≥v[x]） 就有待考量 取的是选与不选的价值的最大值
思路是没问题的 但是只能过6个数据（一半）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int dfs(int x,int spV)
{
if(x>n)
return 0;
//容量不够放下该物品时 只能跳过该物品继续往后走
else if(spV<v[x])
return dfs(x+1,spV);
//容量够时 可以放也可以不放 两种选择 保留最后最大的
else if(spV>=v[x])
//如果放了 容积就会减小 且背包内价值会增大
return max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
记忆化
那么 加上记忆化搜索试试
可以通过
运行时间： 121 ms
运行空间： 4188 KB
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int mem[N][N];//记忆化数组(两个参数所以二维)
int dfs(int x,int spV)
{
if(mem[x][spV])
return mem[x][spV];
int sum=0;
if(x>n)
sum = 0;
else if(spV<v[x])
sum = dfs(x+1,spV);
else if(spV>=v[x])
sum = max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
mem[x][spV]=sum;
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
改成dp
再然后就是改成dp
根据递归搜索树分析 也是可以从大推到1 得出答案
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//递归搜索树里树叶是较大 树根是较小 所以n~1往前推
for(int i=n;i>=1;i--)
{
//遍历体积
for(int j=0;j<=m;j++)
{
if(j<v[i])//如果放不下 直接等于之前的状态
{
f[i][j]=f[i+1][j];
}
if(j>=v[i])//如果放得下 就要取选或不选 结果更大的那种
{
f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
}
}
}
cout<<f[1][m];
return 0;
}
可以发现 dp就是对dfs的优化
减去了递的过程 将递归变成了循环 并利用数组存储算过的值 实现记忆化
那么后续的问题应该就是 我总不能对每道题都写三个解法然后得到dp吧 知道了dp是怎么回事后 就该使用dp的思维去思考问题了
核心不外乎就在于状态表示和状态转移
f[i][j]即状态 其实就代表着某个节点 要清楚他的含义 ij代表什么 fij又代表什么 以及存的是什么max还是总和
然后就是状态转移 我怎么从子问题中计算得到这个节点的状态（从孩子往上推 把已知的孩子的状态转移成当前点的状态）
再用前面的例子来看
楼梯问题：识别子问题 - 每个台阶有多少种上法。构建状态 - 第 i 级台阶的方案数。状态转移 - 第 i 级台阶的方案数等于第 i-1 级和第 i-2 级的方案数之和。
小偷问题：识别子问题 - 在不触动警报的情况下，从前 i 间房子中可以偷窃a的最高金额。构建状态 - 最高金额。状态转移 - 第 i 间房的状态取决于偷或不偷第 i 间房，即 max(前一间房的金额, 前两间房的金额 + 当前房间的金额)。
01背包问题：识别子问题 - 在特定容量下的最大价值。构建状态 - 不同容量下的最大价值。状态转移 - 每个物品决定是否放入背包，即 max(不放入当前物品的价值, 放入当前物品后的总价值)。
首先要思考的是如何将问题分解成可以通过之前计算的结果来解决的子问题，然后构建状态和状态转移方程。这种自底向上的思维方式是DP的核心。
根据现在的思路和y总思路的对比
方向不太一样 但道理一样
现在还停留在从底往上 即把二叉树构造完后 再从叶节点往上走
比如对于某个点选不选 得从左孩子和右孩子两遍考虑
不选其实就是左孩子的值保留一下 什么都不用变
选的话 就是把右孩子的值减去一定容量v 然后再加上一定价值w
而y总是从上往下分析
如果该点不选
就是i-1,j
如果该点选
就是但是不好算出到i的状态
所以同时减去该点
形成i-1,j-v +w
本质得到的公式是一样的 但从底而上就需要绕很多弯
要学会这种从顶而下的思路 把一个问题分解成子问题 这才是真正的dp
dp视角看问题
闫氏dp分析法！
集合角度考虑问题
直接从顶入手 把下面的东西当做已知 我只要知道这个状态是怎么由之前的状态转移而来的即可
而这个转移的分析 使用集合是最好不过了
那么 还是从经典的01背包问题入手
再探01背包
核心不变 分析变成了从上而下 把下当已知 从上而下的话就会有一个问题
若包含该物品 不太好算 得进行一下”曲线救国”
先把第i个物品去掉 空出第i个物品的体积 再在不包含i物品的j-v[i]的情况下 加上第i个物品的权重
（实质是和dfs里分析的一样 不过现在从上往下想 要绕个弯）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//第0个物品无需考虑 f[0][0~m]的最大价值永远是0 初始化成0（全局）
//从第1个物品开始考虑
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//还是一样的 左边的集合是一定存在的（不选）
//右边的集合有可能是空集 （剩余体积不够时）
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
接下来再考虑空间上的优化
分析状态转移方程
注意点就是 看要用的数据是本层的还是上层的 决定是从大到小变量还是从小到大（覆盖前用或是覆盖后用） 不要错用数据
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
//因为 j-v[i]<j 如果从小到大枚举的话 用的就是已经覆盖了的第i层的f[j-v[i]]
//而我们要的是 第i-1层的f[j-v[i]] 所以得在覆盖前就算出来 所以把遍历顺序改成从大到小
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}
之后想问题就是这样 画图 以集合分析 状态表示 状态计算 在写出朴素做法后 再考虑如何优化
完全背包问题
小明期末考试得了全班第一名，妈妈给了他一个背包，可以去超市任意选购，可以选购多种商品，每种商品可以选购多个，但是选择的商品必须都放在背包里。
超市很大，有很多种商品：火腿，雪糕，饼干 ·····。每种商品都摆满了货架。不同商品的体积和价值不同。
在背包能装下的前提下，小明想尽可能带回价值总量高的商品，请问他能带回的商品的最大价值是多少？
这就是完全背包问题。
有 N 种物品和一个背包，每种物品的数量无限。给出了每种物品的体积 v 和价值 w 以及背包的容量 V。
求解 : 背包能装下的前提下，所能获得的最大价值。
例如我们有 4 种物品和一个容量为 5 的背包。这四种物品对应的体积和价值分别是：
物品一：体积是 1，价值是 2。
物品二：体积是 2，价值是 4。
物品三：体积是 3，价值是 4。
物品四：体积是 4，价值是 5。
我们可以选择把 1 个 物品一 和 1 个 物品四 放入背包，体积是 1 + 4 = 5，没有超过背包容量，价值是 2 + 5 = 7。
我们可以选择把 1 个 物品一 和 2 个 物品二 放入背包，体积是 1 + 2 + 2 = 5，没有超过背包容量，价值是 2 + 4 + 4 = 10。
我们可以选择把 2 个 物品一 和 1 个 物品三 放入背包，体积是 1 + 1 + 3 = 5，没有超过背包容量，价值是 1 + 1 + 4 = 6。 还有其它选法。
我们的目的是，找到能被背包装下的物品的最大价值。
与01不同的是 同一样物品可以选多次
朴素写法
不外乎就是添加了一个条件 对于每个物品我可能放多次 那就枚举一下 该物品不放 到 该物品放最大可放数量 的各种情况
\(O(n*m^2)\)#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
//其实就是在01的基础上 加上一个遍历每个物品放多少次的循环
for(int k = 0; k * v[i] <= j; k ++ )//可以无限取 但不能超过剩余容量
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
//f[i-1][j]包含在后半部分 即k=0的时候
cout << f[n][m] << endl;
}
显而易见是tle的
分析
用闫氏dp分析法来看
从三个步骤进行考虑。
步骤一:集合和集合的状态
所谓的集合，就是一些方案的集合。
用 g[i][j] 表示从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。
注意：g[i][j] 不是一个数，是一堆数。
例如 g[2][3] 从前 2 种物品中进行选择，且总体积不大于 3 的各个选法获得的价值的集合。
g[2][3] 的可选择方案包括：
方案一：都不选，总价值为 0。
方案二：选 1 件 物品 1，总价值为 2。
方案三：选 2 件物品 1，总价值为 4。
方案四：选 3件 物品 1，总价值为 6。
方案五：选 1 件物品 2，总价值为 4。
方案六：选 1 件物品 2，一件物品 1，总价值为 6。
所以 g[2][3] = {0，2，4，6，4，2}。
i j 取不同的值，对应不同的 g[i][j]，也就是对应不同的集合。
用 f[i][j] 表示从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。很明显，f[i][j] 就是 g[i][j] 中的最大值。i j 取不同的值，就对应不同的 f[i][j]。我们把 f[i][j] 叫做集合的状态。
例如 f[2][3] 表示从前 2 种物品中进行选择，且总体积不大于 3 的获得的最大价值。
f[2][3] = max(g[2][3] ) = max( 0，2，4，6，4，2) = 6。
g[i][j] 的最大值就是 f[i][j]。
如果我们能把所有集合对应的最大值都求出来，即求出了 f[0][0] ~ f[N][V]， f[N][V] 的含义是在前 N 种物品中进行选择，总体积不大于 V 所获得的最大价值，就是我们要找的答案。
注意，我们不需要把各个集合的所有元素都找出来，只需要求出各个集合的最大值，就能找到答案。下面就是如何求出各个集合的最大值。
步骤二：状态计算
g[i][j] 是从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。
f[i][j] 是从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。
f[i][j] 是集合 g[i][j] 的最大值。
所谓的状态计算是指，如何将把 f[i][j] 算出来。
如果把各个集合 g[i][j] 的状态 f[i][j] 求出来， f[N][V] 就是要找的答案。
回想一下 0 1 背包问题。
01 背包问题把 g[i][j]划分成了 A B 两部分，分别求出这两个部分对应的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，就是 f[i][j]。
01 背包根据是否选择第 i 件物品，也就是第 i 件物品选 0 个还是 1 个，把 g[i][j] 划分成了 A B 两部分，分别求出这两个部分的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。
完全背包问题也是根据第 i 件物品的选择数量，把 g[i][j] 划分成不同的部分，分别求出各个部分的最大值，取各个部分最大值中的最大值，就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。
因为每种物品的数量是无限的，根据第 i 种物品的选择数量可以把 g[i][j] 分为这样几部分：
A 部分： 第 i 种物品选 0 件。
B 部分：第 i 件物品选 1 件。
C 部分： 第 i 件物品选 2 件。
X 部分： 第 i 件物品选 x 件。
因为选择物品的总体积不能大于j，所以第 i 件物品最多选 j / vi 向下取整 件。
对于 A 部分：第 i 件物品选 0 件。
等价于从前 i - 1 种物品中选择商品，且总体积不超过 j 的各个价值的集合，也就是 g[i - 1][j]。
g[i - 1][j] 这个集合中的最大值是 f[i - 1][j] ，所以 A 部分的最大值就是 f[i - 1][j]。
对于 B 部分：第 i 件物品选 1 件，
1 个 i 物品会占据 vi的背包空间，剩下的背包空间为 j - vi 。
可以从前 i - 1 种物品中，选出总体积小于等于j - vi 的物品放入背包。
从前 i - 1 种物品中，选出总体积小于等于j - vi 的各个方案获得的价值集合为 g[i - 1][j - vi ]，
所以 B 部分的元素为 g[i - 1][j - vi ] 中各个元素加上 wi 。
g[i - 1][j - vi ] 中的最大值为 f[i - 1][j - vi ]，所以 B 部分的最大值为 f[i - 1][j - vi ] + wi。
对于 X 部分：第 i 件物品选 x 件，
x 个 i 物品会占据 x * vi 的背包空间，剩下的背包空间为 j - x * vi 。
可以从前 i - 1 种物品中，选出总体积小于等于j - x * vi 的物品放入背包。
从前 i - 1 种物品中，选出总体积小于等于j - x * vivi 的各个方案获得的价值集合为 g[i - 1][j - x * vi ]，
所以 x 部分的元素为 g[i - 1][j - x * vi ] 中各个元素加上 x * wi 。
g[i - 1][j - x * vivi ] 中的最大值为 f[i - 1][j - x * vi ]，所以 B 部分的最大值为 f[i
- 1][j - x * vi ] + x * wi。
例如 g[2][4]。
第二种物品的体积为 2，选择物品的总体积不能超过 4。
所以第二件物品可以选择：0件、1件、2件。
因此 g[2][4] 可以分成以下几部分：
A 部分：第二件物品选 0 件。A 部分的最大值为： f[i - 1][j - 0 * vi] + 0 * wi 。
B 部分：第二件物品选 1 件。B部分的最大值为： f[i - 1][j - 1 * vi ] + 1 * wi 。
C 部分：第二件物品选 2 件。C 部分的最大值为：f[i - 1][j - 2 * vi ] + 2 * wi 。
g[2][4] 中的最大值为 max(A，B，C)。
通过上面分析，我们可以知道，g[i][j] 可以分成若干部分:
A 部分是第 i 种物品选 0 个对应所有选法获的价值的集合，最大值是 f[i - 1][j]。
B 部分是第 i 种物品选 1 个对应所有选法获的价值的集合，最大值是 f[i-1][j - vi] + wi。
X 部分是第 i 种物品选 x 个对应所有选法获的价值的集合，最大值是 f[i - 1][j - x * vi]+x*wi。
所以 g[i][j] 的最大值就是所有子集的最大值中最大的那个，也就是 f[i][j] = max(A, B ，····) 即：
展开式为：
f[i] [j] = max( f[i-1][j] , f[i - 1][j - vi]+w , f[i - 1][j - 2 * vi]
- 2 * w , f[i - 1][j - k * vi ] + k * w , …..) 其中 k <= j / w。
从计算公式可以看出:
f[i][j] 是由 f[i - 1][j - k * vi ] (0 <= k <= j / wi) 和 wi 计算出来的。
f[i][j]的值是可以从前面已经计算出的 f 值求出来。
如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。
步骤三：确定初始值
完全背包问题的有些状态是能够直接确定的。
例如 f[0][0]。
f[0][0] 的含义是:
从前 0 种物品中选择，并且选出的物品总体积小于等于0 时所能得到的最大价值。
总体积小于等于 0，说明一种物品都不能选择。
因此 f[0][0] = 0。同理 f[1][0] = 0，f[2][0] = 0 ··· f[N][0] = 0。
有了这些初始值，通过 i 从 1 遍历 N，j 从 1 遍历 V，第 i 种物品的选择数量 k 从 0 遍历到 j / wi 就能一步步求出所有的 f[i][j] 了。
例如
求 f[1][1]：
f[1][1] = max{f[0][1]，f[0][0] + 2} = max(0，2) = 2。
求 f[1][2]：
f[1][2] = max{f[0][2]，f[0][1] + 2，f[0][0] + 4} = max(0，2，4) = 4。
最后 f[N][V] 就是要找的答案。
优化
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
/*
三重循环会tle 试着把这层循环去掉
for(int k = 0; k * v[i] <= j; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
把k=1 2 3……代入
f[i,j] = Max(f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w...)
f[i,j-v] = Max( f[i-1,j-v] , f[i-1,j-2v]+w , f[i-1,j-3v]+2w...)
可以发现从 f[i,j-v] -> f[i,j] 有很多项相似 也就是说 加入第i个物品 状态变化有规律可言
（本来就是要依靠子问题去更新当前问题的答案 所以提取出上一层与当前层的关系 状态转移方程就好写了）
规律就是 f[i,j]其实就是除第一项外 其他项为f[i,j-v]+w (每一项比原本多了一个w罢了)
那么状态转移方程就可以写成：f[i,j] =Max(f[i-1,j],f[i,j-v]+w)
这样一来就又变成了01背包问题类似的代码
所以得加上个判断 可放入的情况和不可放入的情况
*/
{
//不可放入的情况 直接用上一级答案
f[i][j] = f[i-1][j];
//可放入的情况
if(j>=v[i])
//将找到的规律变形 第一项没规律，保留 其他项有规律 为上一级+w
f[i][j] =max(f[i-1][j], f[i][j - v[i]] + w[i]);
//f[i][j] =max(f[i][j], f[i][j - v[i]] + w[i]);(前面有f[i][j] = f[i-1][j];)
}
cout << f[n][m] << endl;
}
那么可以发现 现在的核心代码和01背包问题的非常相似了
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
唯一的区别在于 01背包是从上一层i-1的状态得来 而完全背包是从这一层的i的状态得来
那么同样也可以用滚动数组优化
这次要的是滚动后覆盖后的值 所以可以从小到大枚举
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++ )
for(int j = v[i]; j <= m; j ++ )//要的是第i层的覆盖后的j-v[i] 所以从小到大枚举
f[j] = max(f[j], f[j-v[i]] + w[i]);
cout << f[m] << endl;
}
对比01与完全
所以到最后 发现和01背包问题只有一个地方不一样——体积是从小到大遍历还是从大到小遍历
而究其原因 就在于 要的是第i-1层的未被覆盖的数据 还是第i层的覆盖后的数据
从大到小是未覆盖的值 从小到大是覆盖后的值
多重背包问题
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
朴素写法
仅适用于数据范围100时
在完全背包的基础上 进行一个物品个数的限制
即每个物品并不是无限个 而是有个数限制的
所以只需要在第三轮的k循环中 加上一个k≤s[i]的限制即可
这种朴素做法 在数据范围小的时候有效 数据范围一大 就会tle了
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N],w[N],s[N];
int dp[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=s[i] && k*v[i]<=j;k++){//只需要加一个k<=s[i]的限制
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+k*w[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
当数据变到1000~2000时 就会tle 多重背包问题 II
优化
多重背包问题，是物品个数是复数个，但又不是无限个。
当作01背包来理解，s个物品当成s次01背包操作。然后优化的话通过 二进制 来优化。
当作完全背包来理解，就是有数量限制的完全背包，而这个数量限制就可以理解成 滑动窗口 的宽度。然后优化通过单调队列来优化。
队列的单调性就是基于f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w,…..,f[i - 1][j - k * v] + k * w，要将前i - 1个物品的方案基础上不停尝试放入第i个物品，遍历取最大值。
f[i - 1][j - k*v] + k *w表示，总空间是j，有且仅有k个物品i，其余空间通过前i - 1个物品填充的最大价值。
多重背包因为有数量限制，向前遍历的个数k是受到数量s限制的。
所以要将max中的每个元素f[i - 1][j], f[i - 1][j - v] + w,…..,f[i - 1][j - k * v] + k * w，通过维护单调队列，来获得当前窗口宽度s范围内的最大值。
并且在j = j + v后，队列中所有元素对应状态与当前背包空间差增加了v，可以多放一个物品i，每个元素对应的价值增加w，全部都加一个w，所以单调性不发生任何变化。
两种优化可以理解成两种思路的进化路线。
二进制优化
把它当成01背包来写 把原物品按照1 2 4 8……拆分出来 这样就物品数量就减成原来的logn多
这次先看代码 再分析问题
#include<iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M
int main()
{
cin >> n >> m;
int cnt = 0; //分组的组别
for(int i = 1;i <= n;i ++)
{
int a,b,s;
cin >> a >> b >> s;
int k = 1; // 组别里面的个数
while(k<=s)
{
cnt ++ ; //组别先增加
v[cnt] = a * k ; //整体体积
w[cnt] = b * k; // 整体价值
s -= k; // s要减小
k *= 2; // 组别里的个数增加
}
//剩余的一组
if(s>0)
{
cnt ++ ;
v[cnt] = a*s;
w[cnt] = b*s;
}
}
n = cnt ; //枚举次数正式由个数变成组别数
//01背包一维优化
for(int i = 1;i <= n ;i ++)
for(int j = m ;j >= v[i];j --)
f[j] = max(f[j],f[j-v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
问题1：为什么最后一项会是f[i−1,j−(S+1)v]+Sw
在完全背包中,通过两个状态转移方程：
f[i,j] = max( f[i−1,j], f[i−1,j−v]+w, f[i−1,j−2v]+2w, f[i−1,j−3v]+3w,…..)
f[i,j−v] = max( f[i−1,j−v], f[i−1,j−2v]+w, f[i−1,j−3v]+2w,…..)
通过上述比较，可以得到 f[i][j]=max(f[i−1][j],f[i][j−v]+w)
再来看下多重背包,
f[i,j] = max( f[i−1,j], f[i−1,j−v]+w, f[i−1,j−2v]+2w, ….. f[i−1,j−Sv]+Sw,)
f[i,j−v] = max( f[i−1,j−v], f[i−1,j−2v]+w, ….. f[i−1,j−Sv]+(S−1)w, f[i−1,j−(S+1)v]+Sw)
怎么比完全背包方程比较就多出了一项?
其实，一般从实际含义出发来考虑即可，这里是在分析f[i,j−v]
这个状态的表达式，首先这个状态的含义是 从前i个物品中选，且总体积不超过j-w的最大价值， 我们现在最多只能选s个物品，因此如果我们选s个第i个物品，那么体积上就要减去 s∗v,价值上就要加上s∗w，那更新到状态中去就是 f[i−1,j−v−s∗v]+s∗w
那为什么完全背包不会有最后一项？
完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，没有最后一项。
问题2：为什么不能和完全背包一样优化
正如上分析 多重背包比完全背包多了一项 而最大值这个操作是不能做什么同时减去一个数 最大值仍不变的 所以不可以简单地从f[i,j-v]直接加上一个w转移到f[i,j]
问题3：二进制优化 为什么正确
首先确认三点：
（1）我们知道转化成01背包的基本思路就是：判断每件物品是取了还是不取
（2）我们知道任意一个实数可以由二进制数来表示，也就是\(2^0\) \(2^k\)其中一项或几项的和。
（3）这里多重背包问的就是每件物品取多少件可以获得最大价值。
分析：
如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。
那么根据数据范围，这样的时间复杂度是\(O(n^3)\),也就是 \(10^9\)，这样是毫无疑问是会TLE的。
假如10个取7个好，那么在实际的遍历过程中在第7个以后经过状态转移方程其实已经是选择“不取”好了。
现在，用二进制思想将其分堆，分成k+1个分别有2k个的堆，然后拿这一堆一堆去问，是取，还是不取，经过dp选择之后，结果和拿一个一个来问的结果是完全一样的，因为dp选择的是最优结果，而根据第二点任意一个实数都可以用二进制来表示，如果最终选出来10个取7个是最优的在分堆的选择过程中分成了2^0=1,2^1=2,2^2=4,10−7=3这四堆，然后去问四次，也就是拿去走dp状态转移方程，走的结果是第一堆1个，取了比不取好，第二堆2个，取了比不取好，第三堆四个，取了比不取好，第四堆8个，取了还不如不取，最后依旧是取了1+2+4=7个
如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。
我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次
二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。
将这一堆苹果分别按照1,2,4,8,16,…..512分到10个箱子里，
那么由于任何一个数字x∈0,1023 都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次
比如：
- 如果要拿1001次苹果，传统就是要拿1001次；二进制的思维，就是拿7个箱子就行（分别是装有512、256、128、64、32、8、1个苹果的这7个箱子）,这样一来，1001次操作就变成7次操作就行了。
这样利用二进制优化，时间复杂度就从 \(O(n^3)\)降到 \(O(n^2logS)\), 从\(4∗10^9\)降到了 \(2∗10^7\)
视频：
单调队列优化
多重背包的原始状态转移方程
f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw)
考虑用完全背包的优化方式来优化这个方程
f(i,j−v)=max(f(i−1,j−v),f(i−1,j−2v)+w,⋯,f(i−1,j−(s+1)v)+(s)w)
写出这个公式好像并不是那么管用
因为 完全背包 是一口气把所有体积全部用掉，即
max(a,b,c,d)=max(a,max(b,c,d))
然而 多重背包 对于每个物品的个数是有限制的，导致我们最终的等式是如下样子： max(a,b,c,d)≠max(a,max(b,c,d,e))
但是，我们可以把这个式子 继续 推导下去，直到背包体积被用到不能再用为止
其中 r=j mod vi，也可以理解为 完全背包 下把当前物品 选到不能再选 后，剩下的 余数
得到 f(i,r)=f(i−1,r)后，我们再利用 完全背包优化思路 往回倒推一遍
会惊奇的发现一个 滑动窗口求最大值 的模型，具体如下：
为了方便观察，把 f(i−1,j)改写成 fj
可能看上去还是有点复杂，为了更方便观察，去掉 w，然后把数组展开成一条链
具体如下图：
于是通过该 滑动窗口 ，我们就能在 线性 的时间里求出 i 阶段里，所有满足 j≡r mod (v)的 f(i,j)
滑动窗口 求 最大值 的实现，只需利用 队列 在队头维护一个 最大值 的 单调递减 的 单调队列 即可
为了更新所有 i 阶段里的状态 f(i,j)，我们只需再额外枚举所有的 余数 r 即可
不要忘记，滑动窗口内部比较最大值的时候，有一个在之前为了方便观察，被删掉的偏移量 w
要记得加上再比较
具体就是 当前下标 和该 最大值的下标 之间差了 x个 v，那么就要加上 x个 w
在上面公式里，还是比较容易看出的吧，就不做额外的推导了
代码
二维朴素版
时间复杂度：O(n×v) 空间复杂度：O(n×v) 滑动窗口的长度为 si+1
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[N][M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j])
-- tt;
q[ ++ tt] = j;
f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[n][m] << endl;
return 0;
}
一维优化
时间复杂度：O(n×v) 空间复杂度：O(v) 和 01背包 的优化类似，观察到 状态转移方程，对于 i 阶段，只会用到 i-1 层的状态
因此可以采用 拷贝数组 或 滚动数组 的写法
拷贝数组写法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
memcpy(g, f, sizeof g);
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j])
-- tt;
q[ ++ tt] = j;
f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[m] << endl;
return 0;
}
滚动数组写法
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j])
-- tt;
q[ ++ tt] = j;
f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[n & 1][m] << endl;
return 0;
}
混合背包问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
- si=−1 表示第 i 种物品只能用1次；
- si=0 表示第 i 种物品可以用无限次；
- si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
分析
学过了01背包 完全背包 多重背包
不难发现他们都是极其相似的
首先01背包用的是从大到小枚举体积 因为它要用的是上一层的数据
完全背包用的是第i层的数据 由此使用从小到大枚举体积
而多重背包有两种理解方式 一是把它当成01背包看 先把所有物品用二进制优化 拆分成多个01背包里的物品 写法就和01完全一样了 从大到小枚举体积 二是当成完全背包来看 把所有的mod余相等的当做同一类物品 这些物品之间相互独立 只需要使用滑动窗口取出每一类中的最大值即可
这里多重背包还是选择使用二进制好些 更容易理解
使用二进制优化的多重背包 与01背包是完全一样的 那么如何合并起来呢
发现01背包不过就是某类物品只能选一次的多重背包吧（s[i]=1)
那么问题就基本解决了
三个问题变成了两个问题
碰到完全背包（无限选的）用一种写法
碰到01背包把它变成s[i]=1的多重背包 再把多重背包进行二进制拆分 合起来用一种写法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct Thing{
int kind;
int v,w;
};
vector<Thing> things;
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
if(s==-1)//如果该物品是01背包的 存-1标记
things.push_back({-1,v,w});
else if(s==0)
things.push_back({0,v,w});
else{//如果是多重背包的 把它拆成多个01背包
for(int k=1;k<=s;k*=2){
things.push_back({-1,v*k,w*k});
s-=k;
}
if(s>0)
things.push_back({-1,v*s,w*s});
}
}
for(auto thing:things){
if(thing.kind==-1)
for(int j=m;j>=thing.v;j--)//01背包 从大到小
dp[j]=max(dp[j],dp[j-thing.v]+thing.w);
else
for(int j=thing.v;j<=m;j++)//完全背包 从小到大
dp[j]=max(dp[j],dp[j-thing.v]+thing.w);
}
cout<<dp[m];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N],s[N];
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
}
//可以不用事先存好 直接现做
for(int i=1;i<=n;i++){
if(s[i]==0)//完全背包 从小到大
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
else//01和多重合在一起
{
if(s[i]==-1)
s[i]=1;//01背包就是该物品只能选一次的情况 直接让s[i]>0 且等于1即可
for(int k=1;k<=s[i];k*=2){
for(int j=m;j>=k*v[i];j--){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
s[i]-=k;
}
if(s[i]){
for(int j=m;j>=s[i]*v[i];j--){
dp[j]=max(dp[j],dp[j-s[i]*v[i]]+s[i]*w[i]);
}
}
}
}
cout<<dp[m];
return 0;
}
//思路虽然更巧妙 直接一气呵成 但是效率反而更低了些 上面138ms 这个166ms
//这个写法用于练手，深入理解用 真正写这类题的话还是用上面的stl 条理清晰
小结
01从大到小枚举体积 完全从小到大枚举体积 多重二进制拆成01 从大到小枚举体积
混合 将01与多重结合一起 完全另判
加维度的背包问题
这个维度添加其实是很灵活的 因为背包问题的限制条件可以有很多
但万变不离其宗 理解f[][]……的含义 这些问题就会迎刃而解
总之还是要画好那个dp分析图
二维费用的背包问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。 输出最大价值。
输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
如果在前面问题的基础上 加上一个限制
比如 背包不仅有容积（体积）的限制 还会有重量的限制
加上这么一个维度 代码应该如何变
其实就是和枚举体积一样 再加一个循环 枚举重量即可
朴素：
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=110;
int v[N],m[N],w[N];//每件物品的体积、重量和价值
int f[N][M][M];
int n,m1,m2;// 物品数量、背包容积上限、背包重量上限
int main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j1=0;j1<=m1;j1++){
for(int j2=0;j2<=m2;j2++){//加一层循环即可 状态转移时也要多一
f[i][j1][j2]=f[i-1][j1][j2];
if(j1>=v[i] && j2>=m[i])
f[i][j1][j2]=max(f[i-1][j1][j2],f[i-1][j1-v[i]][j2-m[i]]+w[i]);
}
}
}
cout<<f[n][m1][m2];
return 0;
}
滚动优化：
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=110;
int v[N],m[N],w[N];
int f[M][M];
int n,m1,m2;
int main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j1=m1;j1>=v[i];j1--){
for(int j2=m2;j2>=m[i];j2--){
f[j1][j2]=max(f[j1][j2],f[j1-v[i]][j2-m[i]]+w[i]);
}
}
}
cout<<f[m1][m2];
return 0;
}
这样一来 以后再加多少维也是一样的
分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
- 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
- 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
从另一个角度 多加一个维度
现在是每类物品里选一个 多了个类这一维
但是因为只能选一个 所以还是可以当做01去写
朴素：
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
//由n种物品变成了n类物品 然后又要在每类里面去选
//所以就是多了一维
int v[N][N],w[N][N],s[N];
int f[N][N];
int n, m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j]; //不选
for(int k=0;k<s[i];k++){
//第i类物品里的第k种
if(j>=v[i][k])
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积
滚动优化
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
//由n种物品变成了n类物品 然后又要在每类里面去选
//所以就是多了一维
int v[N][N],w[N][N],s[N];
int f[N];
int n, m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
//用的上一层的数据 从大到小遍历
for(int j=m;j>=0;j--){
for(int k=0;k<s[i];k++){
if(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[m];
return 0;
}
发现万变不离其宗
再往后可能就是物品分类 且其中可选多个（又分带不带物品数量限制）
背包方案问题
在讨论这个问题之前 先做一道01背包的变形
数字组合
给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示 A1,A2,…,AN。
输出格式
包含一个整数，表示可选方案数。
数据范围
1≤N≤100, 1≤M≤10000, 1≤Ai≤1000, 答案保证在 int 范围内。
发现集合的属性不再是max了
而是count
朴素 17ms
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10010;
int v[N];
int f[N][M];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
//从i个物品中选 且总价值等于0的方案数都是一个（什么都不选也是一种选法）
for(int i=0;i<N;i++)
f[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//空间不够时 不能选第i个物品 此时的方案数为：
f[i][j]=f[i-1][j];
//空间够时 就还得加上选第i个物品（右边集合）的方案数
if(j>=v[i])
f[i][j]+=f[i-1][j-v[i]];
}
}
cout<<f[n][m];
return 0;
}
滚动优化 16ms
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10010;
int v[N];
int f[M];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]+=f[j-v[i]];
cout<<f[m];
return 0;
}
v[i]可不存 循环合并 14 ms
#include<bits/stdc++.h>
using namespace std;
const int M=10010;
int f[M];
int n,m;
int main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++){
int v;cin>>v;
for(int j=m;j>=v;j--)
f[j]+=f[j-v];
}
cout<<f[m];
return 0;
}
越写越熟练了 这种题已经可以直接秒了
接下来正式进入这个背包方案问题
背包问题求方案数
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 109+7 的结果。
数据范围
0<N,V≤1000
0<vi,wi≤1000
数字组合这题问的是所有方案数 就是简单的把原来集合的max属性变成了count属性
而这道题要我们求的是 最大价值的方案数
实际上就是把原本的01背包（求最大价值）和这个变形的01背包（求方案数）做一个结合
在同一dp过程中 同时把这两件事做了即可
思路
f[i][j]记录考虑前i件物品，当前背包容量为j时的最大价值。g[i][j]记录在考虑前i件物品，当前背包容量为j时，达到最大价值f[i][j]的方案数。
1、初始化：f[0][0]不需要管 默认为0 从前0个物品中选体积不超过0的物品的总价值的最大值自然是0 g[i][0] = 1无论考虑多少物品
总存在一种方案使得容量为0的背包达到价值0 即不选择任何物品
2、动态规划更新：
- 遍历物品
i从1到n，和背包容量j从0到m。 - 更新
f[i][j]：如果不取当前物品，则价值为f[i-1][j]；如果取当前物品（前提是j大于等于物品体积v[i]），则价值为f[i-1][j-v[i]] + w[i]，取两者的较大值。 - 更新
g[i][j]：- 如果
f[i][j]的值来源于f[i-1][j]（即不取当前物品），则方案数为g[i-1][j]。 - 如果
f[i][j]的值来源于f[i-1][j-v[i]] + w[i]（即取当前物品），则方案数为g[i-1][j-v[i]]。 - 注意，如果
f[i][j]同时满足上述两种情况，即f[i][j]的值既可以通过不取当前物品也可以通过取当前物品得到，那么g[i][j]应该累加这两种情况的方案数。
- 如果
3、最后，遍历j从0到m，累加所有f[n][j]等于f[n][m]（即最大价值）时的g[n][j]值，得到的总和就是最终的方案数。
问题：
为什么累加所有f[n][j]等于f[n][m]（即最大价值）时的g[n][j]值，得到的总和就是最终的方案数？
我们知道g[n][j]的含义是从前n个物品当中选 体积不超过j的所有达到最大价值的方案数 如果某个方案只选到了k(k是小于n的）就已经达到了最大价值f[n][m] 那它还需要表示为前n个物品中选吗
或者换句话说 所疑惑的这种情况 是否被包含进了g[n][0-m]当中？比如达到最大价值 此时只在k个物品中选了3 即g[k][3] 好像g[n][3]也包括了这个g[k][3]？
分析：
动态规划的状态定义和转移
在0-1背包问题中，状态f[i][j]表示考虑前i个物品，当前背包容量为j时的最大价值。状态g[i][j]记录的是达到这个最大价值的方案数。这里的重点是"考虑前i个物品"并不意味着必须选择第i个物品，也不意味着必须恰好选i个物品。它意味着在前i个物品中进行选择，不超过容量j的条件下可以达到的最大价值及其方案数。
考虑不同数量的物品
当我们说g[n][j]包括了g[k][3]（对于某个k < n和某个容量3），实际上我们是在说：在计算g[n][j]时，我们考虑了所有从第1个物品到第n个物品的可能组合，其中包括了那些仅使用前k个物品达到某个价值的所有方案。
如何理解“考虑前n个物品”中包含了更少物品的情况
动态规划的过程是累积的。当我们在计算f[i][j]和g[i][j]的值时，我们是基于之前所有的计算结果来的。这意味着，如果存在一个最优的方案，它实际上只选取了前k个物品中的一部分，那么这个方案在计算f[k][x]和g[k][x]时已经被考虑过，并且它的价值和方案数被递推到了f[n][j]和g[n][j]。
这是因为，当我们从k递推到n时，如果后面的物品没有被选择（即它们不增加总价值），f和g的值仍然会保留那个最大价值和对应的方案数，因为我们在动态规划中是通过比较和选择最大值来更新状态的。
结论
因此，即使某个最优方案实际上只选择了前k个物品中的一些，这个方案仍然会被包含在最终的g[n][j]中，因为在递推过程中，我们考虑了所有可能的物品组合，包括那些在中途就已经达到最大价值的方案。这就是动态规划的美妙之处：它通过局部最优解的累积，最终得到全局最优解，并能够统计达到这个全局最优解的所有可能的方案数。
现在对于f[][]和g[][]的理解应该有一些了吧
那么再考虑最后一个问题
f[n][m]毋庸置疑是最大答案 我们01背包取最大价值就是取它
根据前面的分析 f[n][0-m]显然就是其他选法的总价值 它对应的选法数量都在g[n][0-m]当中
那么只要发现f[n][j]里有和我们最大价值f[n][m]相等的值 就把那些选法数量（g[n][j])累加起来
朴素做法
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N][N], g[N][N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
// 初始化方案数为1，即不选任何物品的情况
for (int i = 0; i <= n; i++)
g[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j]; // 不选第i个物品
g[i][j] = g[i-1][j]; // 继承不选的方案数
if (j >= v[i]) {
if (f[i][j] < f[i-1][j-v[i]] + w[i]) {
f[i][j] = f[i-1][j-v[i]] + w[i]; // 更新最大价值
g[i][j] = g[i-1][j-v[i]]; // 更新方案数
} else if (f[i][j] == f[i-1][j-v[i]] + w[i]) {
g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod; // 累加方案数
}
}
}
}
int res = 0;
for (int j = 0; j <= m; j++) {
if (f[n][j] == f[n][m]){
res = (res + g[n][j]) % mod;
}
}
cout << res;
return 0;
}
接着就是老套路 消掉一维
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N], g[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
if (f[j] < f[j-v[i]] + w[i]) {
f[j] = f[j-v[i]] + w[i]; // 更新最大价值
g[j] = g[j-v[i]]; // 更新方案数
} else if (f[j] == f[j-v[i]] + w[i]) {
g[j] = (g[j] + g[j-v[i]]) % mod; // 累加方案数
}
}
}
int res = 0;
for (int j = 0; j <= m; j++) {
if (f[j] == f[m]){
res = (res + g[j]) % mod;
}
}
cout << res;
return 0;
}
背包问题求具体方案
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000
因为我们的状态转移一直都是分左右集合去选 所以在求完最大价值的时候
再从最大值反过来推一遍 看i是等于上一层的[i-1,j]还是[i-1,j-v]+w
看这个i有没有被选过 如果被选过 就把这个i记录到答案集里
当前 物品既可以 选 又可以 不选 时，优先 选
int v = V; // 记录当前的存储空间
// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件){
if (g[i][v]){
选了第 i 项物品;
v -= 第 i 项物品的价值;
} else
未选第 i 项物品;
}
因为这里要的是字典序最小的方案（所选物品的编号所构成的序列 物品的编号范围是 1…N）
也就是说 我们要的答案是正的来的 而得到答案是从最大价值反推的 即最大价值要是反着来的 也就是说这次dp要从n做到1 （其实就是最开始dfs改dp的那种写法） 关于这题的字典序好像不是我理解的这么简单（但重点不在于这个顺序 主要还是怎么得出路径）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int w[N],v[N];
int f[N][N];
int path[N],cnt;
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=n;i>=1;i--)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i+1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
for(int i=1,j=m;i<=n;i++)
{
// 判断是否选取了当前物品
if(j>= v[i] && f[i][j]==f[i+1][j-v[i]]+w[i]){
path[cnt++]=i;// 记录选取的物品
j-=v[i];// 更新剩余容量
}
}
for(int i=0;i<cnt;i++)
cout<<path[i]<<" ";
cout<<endl;
return 0;
}
这题就不能去压成一维了 会丢失状态
这题过后可以写一下陪审团这题 也用到了求具体方案
有依赖的背包问题
涉及到树形dp问题
等后面学到了再回头看吧 不过目前的省赛也用不到这种级别的
💬 评论