【算法】【回溯篇】第7节：0-1背包问题
本期任务：介绍算法中关于回溯思想的几个经典问题
作者：岚清子
【算法】【回溯篇】第1节：八皇后问题
【算法】【回溯篇】第2节：解数独问题
【算法】【回溯篇】第3节：正则表达式问题
【算法】【回溯篇】第4节：全排列问题
【算法】【回溯篇】第5节：组合问题
【算法】【回溯篇】第6节：子集问题
【算法】【回溯篇】第7节：0-1背包问题
一、问题描述给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。
问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ （要求使用回溯法）
输入：
n, c = 4, 7
w = [3, 5, 2, 1]
v = [9, 10, 7, 4]
输出：
20
[0, 2, 3]
二、算法思路
0-1背包问题是典型的“多阶段决策最优解”问题：每个物品决策一次（拿或者不拿），共决策n次（n为物品数量）；最优解是背包容量限制下的最大价值。
本题使用回溯算法暴力穷举所有可能的排列方式，并通过剪枝策略进行优化。
暴力穷举，每个物品都可能有2种（拿或者不拿），所有可能方式共有2n2^n2n，穷举过程遵循深度优先搜索规则。
维护一个长度为n的数组res，用于保存每个物品的是否取。
剪枝策略：背包容量无法容纳当前物品时，剪枝跳过。
结算情形：所有物品遍历完成时。
示例对应的递归树如下，其中f(0,7,0)f(0,7,0)f(0,7,0)代表装入编号为0的物品前，背包容量为7，当前总价值为0：
class Package01():
def __init__(self, n, w, v):
self.n = n # 物品数量
self.w = w # 物品重量
self.v = v # 物品价值
self.max_v = 0 # 记录最大价值
self.cur_ls = [False] * n # 记录当前物品清单
self.res = [] # 记录最大价值对应的物品清单
def package01(self, cur_c, cur_v=0, index=0):
if index == self.n: # 当遍历完所有物品进行结算！！！
if self.max_v = self.w[index]: # 背包装的下当前物品时
self.cur_ls[index] = True
self.package01(cur_c - self.w[index], cur_v + self.v[index], index + 1)
self.package01(cur_c, cur_v, index + 1) # 不装当前物品
def main():
n, c = 4, 7
w = [3, 5, 2, 1]
v = [9, 10, 7, 4]
pk = Package01(n, w, v)
pk.package01(7, 0, 0)
print(pk.max_v)
print([i for i, _ in enumerate(pk.res) if _])
if __name__ == '__main__':
main()
输出结果：
20
[0, 2, 3]
作者：岚清子
