背包九讲——背包问题求具体方案

摆烂小白敲代码

1871人浏览 · 2024-11-07 12:00:23

摆烂小白敲代码 · 2024-11-07 12:00:23 发布

背包问题求具体方案

1. 01 背包问题

题目：12. 背包问题求具体方案 - AcWing题库

背包问题第九讲——背包问题求具体方案

背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最大化某种价值或利益。问题的一般描述是：有一个背包，其容量为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博客

到现在为止，背包九讲问题都更新完了，但是学习不可停止哦，以后我会分享其他的算法，或者再去更新一些知识点和例题，欢迎大家关注。笔者水平有限，一些地方做的不足的地方和需改善的地方大家可以提出来，大家有不明白的地方随时可以私信我，互相学习，大家一起加油！

执笔至此，感触彼多，全文将至，落笔为终，感谢大家支持。