算法思想参考北大慕课曲奶奶算法分析课件, 课件原题是对应完全背包, 稍微改下就能应用到当前的01背包
看追踪图解的时候请分屏结合代码一起看``, 有条件最好可以把代码里面的st表也打印出来对照~
C++ 代码
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int st[N][N];
int v[N], w[N];
signed main()
{
scanf("%d%d", &n, &m);
for (int i = n; i >= 1; i--) scanf("%d%d", &v[i], &w[i]); //为了字典序, 倒着读
// 倒着读正着dp, 结合下面if里面的f[i][j] <= f[i - 1][j - v[i]] + w[i], 字典序是往目前的n方向偏的
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
st[i][j] = st[i-1][j];
f[i][j] = f[i-1][j];
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];
st[i][j] = i;
}
}
}
int i = n, j = m; // 初始化寻路起点
while (st[i][j])
{
//当前st[i][j]里面记录的是现在选中的点, 由于dp的时候是倒着的, 现在倒回来就能直接输出了
printf("%d ", n + 1 - st[i][j]);
int t = st[i][j]; // 当前点最后选中的物品t
// 把当前选中的点的体积去掉就能把j往前推
j -= v[t];
// 标记函数是记录的物品最大标号, 往回的的时候把这个物品t去掉之后, 就能把i推回到t之前
i = t - 1;
}
return 0;
}
可以把DP理解成一个在 拓扑图 内找最短路问题
每个状态
f[i][j]
都是一个点,状态的转移就是一条边初始状态
f[0][0]
就是起点,目标状态f[n][m]
就是终点然后对于 背包问题求具体方案 就可以转换成 最短路问题求路径
这样就会很简单了
感觉这个ppt有点抽象
可是我还没学到拓扑图QAQ..
其实这个ppt结合代码看还是挺好懂的, 待我更新下友好版代码再加点注释~
已更新, 参考下代码应该就可以了~
hh很棒