一份代码只换一个方向
写一个 knap(items, cap, back)：back 为真时容量倒着循环（0/1 背包），为假时正着循环（完全背包）。输出「0/1 的答案/完全的答案」。 本路线的物品：(重 3 值 8)、(重 4 值 9)、(重 5 值 11)
滚动数组在做什么
第 1 步：两行就够：旧的一行、新的一行 第 2 步：第 1 件：由旧行算出新行 第 3 步：新行变成下一轮的旧行 第 4 步：第 2 件：由旧行算出新行 第 5 步：新行变成下一轮的旧行 第 6 步：第 3 件：由旧行算出新行 第 7 步
什么时候能滚（C++）
一个 DP 能用滚动数组，条件是【0】。
滚了之后哪样没变（C++）
用滚动数组优化之后【0】。
两张表各占多少格
三件物品、容量 10。二维表是 (件数+1) × (容量+1)，一维表就是 容量+1。运行下面这段程序： #include <algorithm> #include <iostream> #include <s
两种写法算得一样吗
二维写法取 dp[3][10]，一维写法取 dp[10]。运行下面这段程序： #include <algorithm> #include <iostream> #include <string> #inc
把二维改成一维
二维版的转移是 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)。把它改写成只用一个一维数组的 knap1d，输出容量 10 的最大价值。 本路线的物品：(重 3 值 8)、(重 4 值 9)、(重
答案和用掉的格子一起报
写出一维版，输出「容量 10 的最大价值/这个一维表的长度」。 本路线的物品：(重 3 值 8)、(重 4 值 9)、(重 5 值 11)，写成 vector<pair<int, int>>，auto [w, v]
答案与空间一起摆出来
把二维版和一维版都写出来，输出四样：二维答案/一维答案/二维格子数/一维格子数。 本路线的物品：(重 3 值 8)、(重 4 值 9)、(重 5 值 11)，写成 vector<pair<int, int>>，aut
这张表占多少内存
第 1 步：一格约等于 10 MB 第 2 步：上：5000×5000 个 int 第 3 步：下：栈只有约 8 MB 第 4 步：放局部：栈装不下，崩溃 第 5 步：滚成一维：只剩 5000 个 int dp[5000][5000] 大约