[01背包] 背包问题求具体方案(01背包+求方案数+思维)

文章目录

0. 前言

相关：

• [背包] 背包问题算法模板(模板)

1. 01背包+求方案数+思维

12. 背包问题求具体方案

求方案数也是背包问题、dp 的一大考点。本题仅以 01 背包为例。其实所有的 dp 问题都可以求出来状态转移的具体方案。所有的状态构成图，针对于 min 转移的话，其实就是求最短路路径，针对 max 转移的话，其实就是求最长路路径。

状态转移方程为 f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi)，其实就是决策出每个 i 的状态转移到底是从第一项还是第二项转移过去的。那么当我们求完之后倒着推一遍就能得到转移过来的最短路径了。 例如，答案 f[n]m] 转移情况有三种：

• 当 f[n][m]=f[n-1][m] 的时候，不选第 n 个物品，可以得到最大价值
• 当 f[n][m]=f[i-1][j-vi]+wi，选择第 n 个物品，可以得到最大价值
• 当 f[n][m]=f[i-1][j-vi]+wi 或者 f[n][m]=f[n-1][m]，第 n 个物品选不选都可以得到最大价值

注意：

• 需要使用两维状态，需要 i 这个序号，最后需要输出
• 因为本题需要按字典序输出，那么肯定是从第 1 个物品开始考虑
  • 当 f[1][m]=f[2,m-v[1]]+w[1] 选第一个能得到最优解
  • 当 f[1][m]=f[2,m]，不选第一个能得到最优解
  • 当 f[1][m]=f[2,m-v[1]]+w[1]=f[2,m] 选不选第一个都能得到最优解。但还是选第一个，因为它字典序最小
• 但是，得到字典序路径是需要反着倒推的，所以枚举物品的时候就从第 n 个物品枚举到第 1 个物品，这样逆序枚举。求出来的当前背包最大价值应为 f[1][m]，这样是很灵活方便的
  • 代码一定理解透本质，灵活多变

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

int n, m;
int v[N], w[N];
int f[N][N]; 

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]);
        }
    
    // 在此，f[1][m]就是最大数量
    int j = m;
    for (int i = 1; i <= n; ++i) 
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    return 0;
}

---

一般的，开辟一个数组专门用以记录状态转移过程也能完成状态记录。这是更为一般的方式。

在此，有递归、非递归两种写法。参考大佬题解：背包问题求具体方案(递归版本）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

int n, m;
int v[N], w[N];
int f[N][N], g[N][N];

// 递归打印，参考:https://www.acwing.com/solution/content/19760/
void print(int x,int y)
{
    if(x == n + 1) return;
    int k = way[x][y];
    //判断是否选择了第x件物品
    if(k) cout<<k<<' ';//在递归函数的上面为由根节点到叶子节点进行操作
    print(x+1,y-v[k]);
    //在递归函数的下面进行操作，为叶子节点遍历完了，回溯由子节点到根节点进行操作

}

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]) {
                if (f[i][j] <= f[i + 1][j - v[i]] + w[i]) { 
                    f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
                    g[i][j] = i;
                }
            }
        }
    
    // 递归
    // print(1, m);
    
    // 非递归
    int j = m;
    for (int i = 1; i <= n; ++i) {
        if (j >= v[i]) {
            if (g[i][j]) {
                cout << g[i][j] << ' ';
                j -= v[i];
            }
        }
    }

    return 0;
}