历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 12. 背包问题求具体方案【01背包 + 背包DP输出方案】原题链接中等

作者：

一只野生彩色铅笔 , 2021-06-25 17:10:17 , 所有人可见 , 阅读 7838

68

22

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

有 $N$ 件物品和一个容量为 $V$ 的背包

第 $i$ 件物品的体积是$v_i$, 价值是$w_i$,每件物品只能使用一次

求解一种方案，使得选择的物品的 总体积 不超过背包的 最大容量，且 总价值 最大

输出 字典序最小的方案

分析

本题是 背包DP 的经典变种模型 背包DP输出方案

输出方案 其实就是输出方案的 转移路径

我们先做一遍正常的 背包DP ，然后从 目标状态 倒推回 初始状态 的整个 转移路径 即可

说的白话一点就是，在考虑第 i 件物品时，选择了选还是不选的策略到达了第 i+1 件物品

伪代码如下：（参考oi wiki）

int v = V;  // 记录当前的存储空间

// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件)
{
  if (g[i][v])
  {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

当然也可以从 拓扑图 的角度来 分析理解，这次不额外展开，具体可以参考下面这篇博客，里面也有 DFS 的写法

AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】

这里主要展示迭代的写法（其实就是在跟踪状态转移的路径）

题目里还要求了输出 字典序最小的方案

而在倒推 状态转移路径 的时候，只能在 分叉转移 的时候，即当前物品既可以选又可以不选时，优先选

因此，我们本题的 背包DP 需要倒过来（从N递推到1）做，然后再 从1倒推回N 找出路径

这样在抉择时，如果出现 分叉转移，我们就优先选当前物品即可

01背包模型 $\mathrm{f[i][j]}$

状态表示$f(i,j)$—集合： 考虑后 i 个物品，且当前已使用体积不超过 j 的方案

状态表示$f(i,j)$—属性： 该方案的价值为最大值 $\max$

状态转移$f(i,j)$： $f(i,j) = \begin{cases} 不选第i个物品： &\max\{f(i+1,j)\} \\\ 选第i个物品：&\max\{f(i+1,j - v_i) + w_i\} \end{cases}$

Code

时间复杂度：$O(N \times V)$

路径追踪的递归写法可以参考这篇博客
AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】

#include <iostream>

using namespace std;

const int N = 1010;

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

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;
}

16 评论

醒了不起的盖兹比 2023-04-26 00:53

立志走遍铅笔哥每一篇题解

Catw1thu 2023-03-10 23:10

感觉这里的f(i,j)不是考虑后i个物品，而是考虑第i个物品到第n个物品

糖豆 2023-05-17 08:50

你是对的，举个栗子： 1 2 3 4 5 6 7 8 9 10,如果是从前往后到第5个，f(5,j)就是正常的前5个，如果是从后往前就是：10 9 8 7 6 5,这其实是6个。

awdasfasfa 2024-02-04 16:21

为什么一维数组错了
#include [HTML_REMOVED]
using namespace std;
const int N = 1010;
int n, m;
int w[N], v[N];
int f[N];
int path[N], cnt;
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–)
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
for (int i = 1, j = m; i <= n; i)
{
if (j >= v[i] && f[j] == f[j - v[i]] + w[i])
{
path[cnt ] = i;
j -= v[i];
}
}
for (int i = 0; i < cnt; ++ i) cout << path[i] << ” “;
return 0;
}

阿飞_14 2025-03-21 17:07 · 江西

因为你下面输出序列的dp无法满足上一层的一维是结果化的，二维才能表示过程，一维的话要这样做#include[HTML_REMOVED]
using namespace std;

const int N = 1005;

int dp[N];
//体积为j的最优解的序列
vector[HTML_REMOVED] g[N];

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

int n, v;
cin >> n >> v;

for(int i = 1; i <= n; i++) {
    int vi, wi;
    cin >> vi >> wi;
    for(int j = v; j >= vi; j--) {
        if(dp[j] < dp[j - vi] + wi) {
            dp[j] = dp[j - vi] + wi;
            g[j] = g[j - vi]; 
            g[j].push_back(i); 
        } else if(dp[j] == dp[j - vi] + wi) {
            vector<int> temp = g[j - vi];
            temp.push_back(i);
            if(g[j] > temp) {
                g[j] = temp; 
            }
        }
    }
}
for(int i = 0; i < g[v].size(); i++) {
    cout << g[v][i] << " ";
}
cout << endl;

return 0;

}