背包九讲——背包问题求具体方案
目录
背包问题求具体方案
1. 01 背包问题
题目：12. 背包问题求具体方案 - AcWing题库
算法思路：
代码实现：
2. 多重背包问题
算法思路：
3. 完全背包问题
算法思路：
代码实现：
背包问题第九讲——背包问题求具体方案
背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最大化某种价值或利益。问题的一般描述是：有一个背包，其容量为C；有一组物品，每个物品有重量w和价值v。目标是选择一些物品放入背包，使得它们的总重量不超过背包容量，同时总价值最大。
背包问题涉及到了三种基础的背包：01背包、多重背包、完全背包，我们要根据在这几个背包的基础上去计算在获得最大价值的情况下，有几种方案，并输出具体的方案，是求背包问题方案数的进阶版，这个需要打印具体方案了。
背包问题求具体方案
上一篇说了一下背包问题求方案数，下面进行深化一点就是求具体方案了。同上一篇这些问题都是在01背包、多重背包、完全背包基础上演化来的，求具体方案问题会问你一种具体方案（编号序列的字典序最小）或者打印所有具体方案，一般的问题都是问你第一种。若为第二种问法，建议使用C语言的printf进行打印，因为打印所有具体方案，当数据量很大时会有很多输出，使用printf会比cout快一点。根据问题的具体类型，常见的背包问题包括：
1. 01 背包问题
0-1背包问题是指每个物品只有0跟1两种选择即只能选择放或不放，不能分割。给定一组物品，每个物品都有自己的重量和价值，在不超过背包容量的前提下，选择一些物品，使得总价值最大。
题目：12. 背包问题求具体方案 - AcWing题库
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000输入样例
4 5 1 2 2 4 3 4 4 6输出样例：
1 4
算法思路：
题目要求了输出字典序最小，所以尽量靠前去，尽管有不同的方案所获得最大价值一样，但是要考虑字典序最小，所以一定要选前面的，比如选1，3，5和2，3，4所获得的价值一样，但是要选1，3，5，所以后面遍历下标从小到大遍历的。上面说明了如果第一个物品属于最优解的一种，一定要选它，这样问题就转化成了从2~N寻找最优解问题，以此类推。
状态定义f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值
状态转移：f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i])
f[i][j]的上一个状态就是从i+1转移过来的，因为我们定义从第i个物品到最后一个物品，第i+1个物品到最后一个之间的数量是不是比第i个物品到最后一个物品少。f[i+1][j]是不选第i个物品，f[i+1][j-v[i]]+w[i]是选第i个物品。因为我要在所有f[i][j]当中选择一个最大值，所以前面我管不管的先初始化为不选，往后如果背包容量大于体积，那我再看看是选了这个物品总价值是否增大，如果增大就更新，不增大就保持原来。这样写避免了两重判断最优解，会有两个max，这样只有一个max，其实，好好想一想，我前面先初始化为不选，毫无影响的，后面大于体积那我就走if，不大那就不选呗，那不还是初始化为不选。
最后那一段就是查找最优路径了。首先我先初始为背包容量，面对第i个物品时，若背包剩余容量大于体积并且从上一个状态转移过来，选了第i个物品，那它一定是最优解，并且是字典序是最小的，因为我是正序遍历的。
代码实现：
#include<iostream>
using namespace std;
int N,V;
int v[1005],w[1005],f[1005][1005];//f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值
int main(){cin>>N>>V;for(int i=1;i<=N;i++){cin>>v[i]>>w[i];}for(int i=N;i>=1;i--){//逆序取物，因为f[i][j]定义从i到最后for(int j=0;j<=V;j++){f[i][j]=f[i+1][j];//先初始化为不选第i个物品if(j>=v[i]){//如果背包剩余容量大于物品体积f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);//那就寻找最优解，到底是选还是不选所获得总价值更大}}}int j=V;for(int i=1;i<=N;i++){if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){//如果f[i][j]从f[i+1][j-v[i]]+w[i]转移过来，那路径就一定是最优路径cout<<i<<" ";j-=v[i];//选了就减去背包容量，方便下次寻找}}return 0;
}2. 多重背包问题
多重背包问题是指每种物品可以取有限次。给定一组物品，每种物品都有自己的重量、价值和一个数量限制，在不超过背包容量的前提下，选择物品的组合使得总价值最大。
算法思路：
多重背包跟01背包解法没有太大的区别，无非就是多重背包需要先进行二进制拆分，把它拆分成01背包再利用01背包求具体方案的模板进行求解。
3. 完全背包问题
完全背包问题是指每种物品可以无限取用，可以理解为无限使用。给定一组物品，每种物品都有一个重量和价值，在不超过背包容量的前提下，选择物品的组合使得总价值最大。
算法思路：
完全背包求具体方案可能就让你写第几种物品选择了几种，例如，第一种物品选择了2个，第二种物品选择了0个...这样无非又是动态规划问题。可以看一下下面思路。
-
定义状态：
- 定义
dp[w]为当背包容量为w时能够取得的最大价值。 - 使用
count[i][w]来记录当背包容量为w时，物品i被选择了多少个。
- 定义
-
状态转移方程：
- 对于每个物品
i，如果它的重量weight[i]小于等于当前背包容量w，则可以选择该物品。 - 状态转移公式为： dp[w]=max(dp[w],dp[w−weight[i]]+value[i])dp[w] = \max(dp[w], dp[w - weight[i]] + value[i])dp[w]=max(dp[w],dp[w−weight[i]]+value[i])
- 在此过程中，需要同时更新
count[i][w]来记录物品的选择次数。
- 对于每个物品
-
初始化：
- 当不选择任何物品时，
dp[0] = 0，其他状态初始化为 0。
- 当不选择任何物品时，
-
最终结果：
dp[W]为在背包容量W时能够取得的最大价值。- 通过
count数组可以得出每种物品的选择次数。
代码实现：
#include <iostream>
#include <vector>
using namespace std;int knapsack(int W, const vector<int>& weight, const vector<int>& value, int n) {vector<int> dp(W + 1, 0);vector<vector<int>> count(n, vector<int>(W + 1, 0));// 动态规划求解完全背包问题for (int i = 0; i < n; ++i) { // 对每个物品进行处理for (int w = weight[i]; w <= W; ++w) { // 每个物品可以被多次选择if (dp[w] < dp[w - weight[i]] + value[i]) {dp[w] = dp[w - weight[i]] + value[i];count[i][w] = count[i][w - weight[i]] + 1; // 记录物品i的选择次数}}}// 输出结果cout << "最大价值: " << dp[W] << endl;cout << "每个物品的选择数量: " << endl;for (int i = 0; i < n; ++i) {cout << "物品 " << i + 1 << ": " << count[i][W] << " 个" << endl;}return dp[W];
}int main() {int W = 10; // 背包容量vector<int> weight = {2, 3, 4}; // 各个物品的重量vector<int> value = {3, 4, 5}; // 各个物品的价值int n = weight.size();knapsack(W, weight, value, n);return 0;
}上一篇博客：背包九讲——背包问题求方案数-CSDN博客
到现在为止，背包九讲问题都更新完了，但是学习不可停止哦，以后我会分享其他的算法，或者再去更新一些知识点和例题，欢迎大家关注。笔者水平有限，一些地方做的不足的地方和需改善的地方大家可以提出来，大家有不明白的地方随时可以私信我，互相学习，大家一起加油！
执笔至此，感触彼多，全文将至，落笔为终，感谢大家支持。