0/1 背包时间方向：数据结构与算法实验

互动实验 1 / 5

只有一件重量 2、价值 3 的物品，容量 4，正确最大价值是多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<int>good(5),wrong(5);
for(int c=4;c>=2;--c)good[c]=max(good[c],good[c-2]+3);
for(int c=2;c<=4;++c)wrong[c]=max(wrong[c],wrong[c-2]+3);
cout<<good[4]<<" "<<wrong[4];
}

只有一件重量 2、价值 3 的物品，容量 4，正确最大价值是多少？

思路提示

单件物品最多使用一次。

可以回到前一步复查示例，理解后再独立验证。

互动实验 2 / 5

错误的正序更新会算出多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<int>good(5),wrong(5);
for(int c=4;c>=2;--c)good[c]=max(good[c],good[c-2]+3);
for(int c=2;c<=4;++c)wrong[c]=max(wrong[c],wrong[c-2]+3);
cout<<good[4]<<" "<<wrong[4];
}

错误的正序更新会算出多少？

思路提示

更新容量 4 时重用了本轮容量 2 的结果。

可以回到前一步复查示例，理解后再独立验证。

互动实验 3 / 5

0/1 背包一维容量为什么倒序？

选择符合算法原理和适用条件的一项。

互动实验 4 / 5

要求恰好装满时，能否把所有状态初始化为 0？

选择符合算法原理和适用条件的一项。

互动实验 5 / 5

二维状态压成一维时应先检查什么？

选择符合算法原理和适用条件的一项。

0/1 背包时间方向

准备探索0/1 背包时间方向

只有一件重量 2、价值 3 的物品，容量 4，正确最大价值是多少？

错误的正序更新会算出多少？

0/1 背包一维容量为什么倒序？

要求恰好装满时，能否把所有状态初始化为 0？

二维状态压成一维时应先检查什么？

引导实验已完成。

把发现，变成独立解决问题的能力。