背包型特征

为什么背包型要用体积值作为维度?

• 可以通过画搜索树来理解
• 因为在不同的选择当后, 存在相同的体积子问题.
• 但是, 不能仅仅用体积作为维度. 因为虽然体积相同, 但是这个体积剩下的选择不一样, 可以通过对比图中体积4的分支有所不同, 我们需要增加一个维度来识别我们取的是前多少个数. 我们可以知道通过取前三个数, 我们能得到体积4, 通过取前4个数, 我们能得到不一样的体积4.
  • 说得有点抽象. 也就是 路径 2->5, 以及5->2, 是前3个数. 路径7是前4个数.
  • because the subproblems of value 4, as we see, are different. under value 4, we are not sure which elements we have been used.
  • what if we use a visited array to record the elements we have been used along the path, and then backtrack. we still need to go through the array to search . because each path is independent of other paths. it doesn't help reduce time complexity. Therefore, we need to add another to record the state.
• 所以我们要定义dp[i][S], 表示前i个物品来组成体积为S 的xxxx
• 物品的顺序不影响最终的结果,会影响表中的值

可用滚动数组优化

题目

1. Backpack
2. Backpack II
3. 变形, 把一个数组[1, 24, 5, 6]平分
4. Minimum adjustment cost
5. K-sum
6. Backpack IV
7. Backpack III