01背包问题（最优解问题）
就是现在有一个体积为c的背包，现在要装一些东西，这些东西有体积和价值，现在要求一个最优解，
也就是在c之内，放最大价值的物品
目的是限制化重量下，求最大价值
蛮力法
使用蛮力法就是，遍历每一种方案，对于每一个物品都要枚举一次看看是否放入背包，最后比较每一种方案的价值
（遍历每一种方案）
def bag01_force(n,w,value,weight):
"""
蛮力法求解
n ：物品数量
w ：背包体积
value ：物品价值
weight ：物品体积
return 能放入的物品最大价值
"""
# 返回值
res = 0
# 蛮力法 遍历每一种方案，n个物品，每一个物品都有两种状态，放入或者不放入背包，所以一共有
# 2**n种状态
# 1 0 1
# 2 10 01 00 11
for i in range(2**n)：
# 方案体积
total_weight = 0
# 方案价值
total_value = 0
# 第二层循环，每一种方案下遍历每一件物品
for j in range(n):
# 判断方案i是否选择了物品j，如果被选择，那么背包中体积与价值发生变化
# i是一个整数，j是一个0到n-1的整数
# 1<<j 表示1左移j位
# 位与运算，结果如果不为0，那么表示在该位上都为1，也就是j被选择了
if (i & (1<<j)) != 0:
total_weight += weight[j]
total_value += value[j]
# 判断，目的体积要小于背包容量
if total_weight <= w:
# 求最大价值
res = max(res,total_value)
return res“””
当i==0时，代表没有选择物品
i==1,第一种方案，j==0，第一个物品 1<<0 = 1 1 & 1 =1 代表在第i==1种方案下，第j==0（第一个物品）
被放进背包。
j == 1 表示第二个物品 1 << 1 = 10 1 & 10 = 0 没有被选择
j == 2,3,4…n-1
i == 2 j==0,1,2,,3…n-1
O(n) = n * 2 **n
“””
减治法
把一个大问题分解成几个小问题，递归求解子问题，合并子问题的解得到大问题的解（缩小问题规模）
第i个物品价值:value[i] 体积:weight[i],背包容量C
第i个物品，要么选，要么不选
1、前n-1个物品选择中，容量 C-weight[n] 选n
2、前n-1个物品选择中，容量 C 不选n
递归
def bag01(weight,value,n,c):
# 背包容量为0或者物品数量为0,递归出口
if c == 0 or n == 0
return 0
if weight[n-1] > c:
return bag01(weight,value,n-1,c)
return max(value[n-1] + bag01(weight,value,n-1,c - weight[n-1]),bag01(weight,value,n-1,c))循环(动态规划)
def bag01(n,c,weight,value):
# 保存最终结果，c+1（存储了0-c的所有结果）
dp = [0] * (c + 1)
# 第一层循环，遍历物品
for i in range(n):
# 倒序遍历
# 枚举第i物品，容量从c开始，枚举容量从大到小
for j in range(c,weight[i] -1,-1):
# 当前容量为j时，选或者不选第i个物品，取最大值，来确定这个物品是否放入背包
# 如果加入，dp[j] == dp[j - w[i]] + v[i]
# 不加入，dp[j]
dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
return dp[c]分治法
分治法是把一个问题分解成子问题，再把子问题分解成更小的问题，直到子问题容易解决就把解合并。（分解问题）
n个物品，重量w1,w2,w3。。。wn。价值v1,v2…vn
容量为c，c-weight[i] > 0
max(value)
把物品分成两组，考虑每一组是否被选择。
#递归
def bag01(n,c,weight,value):
# 物品数量为0或者背包容量为0
if n==0 or c == 0:
return 0
# 物品不能放入背包
if weight[n-1] > c:
# 不考虑当前物品
return bag01(n-1,c,weight,value)
else:
# 递归解决剩下问题，（放和不放，最大值）
return max(value[n-1] + bag01(n-1,c-weight[n-1]),bag01(n-1,c.weight,value))迭代（循环模拟递归，需要用变量来保存中间状态）
def bag01(n,c,weight,value):
dp = [0] * (c+1)
for i in range(1,n+1):
for j in range(c,weight[i-1] -1,-1):
dp[j] = max(dp[j],dp[j-weight[i-1]]+value[i-1])
return dp[c]
分治法重点是把物品不断的切割，分别考虑每组物品是否被选择
减治法重点不断缩减背包容量，利用放入或者不放入物品
变治法
对问题进行变形，将问题转换成简单的问题
例如：减小问题规模n —— n/2
背包容量从小到大排序，利用分治法把大问题分解为小问题，然后减治法把子问题合并起来
def bag01(weight,value,c,n):
# 中间状态，f[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值
f = [[0 for j in range(c+1)] for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,c+1):
# 第i个物品不能放
if j < weight[i-1]:
# 第i个物品取第i-1个物品的状态
f[i][j] = f[i-1][j]
else:
# 取第i-1个物品的状态和第i个物品放入的状态的较大值
f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]])
return f[n][c]时空权衡（基于计算机）
如果想要时间效率最优，可以用动态规划，如果想要空间占用少，可以使用贪心或者滚动数组（将多余空间删去）
滚动数组（模2）
占用空间较小
def bag01(weight,value,c,n):
f = [[0 for j in range(c+1)] for i in range(2)]
for i in range(1,n+1):
for j in range(1,c+1):
# i物品数 j容积
# 第i个物品不进背包的情况(% 取余)
f[i % 2][j] = f[(i-1) % 2][j]
# 第i个物品不能放
if j >= weight[i-1]:
# 第i个物品取第i-1个物品的状态
f[i % 2][j] = f[（i-1） % 2][j]
else:
# 取第i-1个物品的状态和第i个物品放入的状态的较大值
f[i % 2][j] = max(f[i % 2][j],f[（i-1） % 2][j-weight[i-1]])
return f[n][c]动态规划（解决最优解问题的方法）
一种求解多阶段决策问题的方法，一种面向最优化的递归计算技巧
用于求解分段函数的最值。它通过以一定顺序对复杂问题进行分解，以避免重复的计算。
并以类似递推的方式，通过对更小的子问题的解的组合得到原问题的解。
1、分解问题，对于分解之后的若干子问题·，定义一个状态。通过状态转移方程，将子问题的解转化成原问题的解
对于每一个物品i，枚举它的体积j，计算f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])，
def bag01(weight,value,c,n):
# 中间状态，f[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值
f = [[0 for j in range(c+1)] for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,c+1):
# 第i个物品不能放
if j < weight[i-1]:
# 第i个物品取第i-1个物品的状态
f[i][j] = f[i-1][j]
else:
# 取第i-1个物品的状态和第i个物品放入的状态的较大值
f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]])
return f[n][c]贪心（最优解问题）并不总能得到全局最优解
n件物品放入容量为c的背包中，（可不全部放入）使得背包中物品价值最大。
较好的近似解
问题分解，求每一个小问题的最优解。
1、单位重量价值最大的物品先放，直到背包无法再放。（贪心选择性质）
def bag01(value,weight,n,c):
# 物品的单位重量价值
meimei = [value[i]/weight[i] for i in range(n)]
# 排序（逆序，从大到小的顺序）按照价值重量比排序后的物品索引数组
meimei = sorted(range(n),key=lambda i: meimei[i],reverse=True)
total_value = 0
# 是否放入背包的数组
bag = [0] * n
for i in meimei:
if weight[i] <= c:
bag[i] = 1
total_value += value[i]
c -= weight[i]
else:
# 计算部分放入背包
bag[i] = c/weight[i]
total_value += value[i] * (c/weight[i])
break
return total_value,bag迭代改进（优化算法）并不总能得到全局最优解，较好的近似解
基本思想：每一次迭代中，根据当前解，确定一个方向，并且在方向上的解有所改进。
具体步骤：
1、初始化解，将解初始化为一个可行解。（全放和全不放）
2、迭代改进，每一次迭代中，选择一个方向，感觉该方向的优化目标，生成一个新解，并比较当前解。
3、判断终止条件，判断解是否满足问题要求
def bag01(value,weight,n,c):
# 初始化解
select_items = [0] * n
total_value = 0
while c >0:
# 计算性价比,并按照性价比从大到小排序
ratios = [(value[i] / weight[i],i) for i in range(n)]
ratios.sort(reverse=True)
# 尝试放入物品
for ratio,i in ratios:
if weight[i] <= c:
c -= weight[i]
select_items[i] = 1
total_value += value[i]
# 判断终止条件
if all(select_items):
break
return total_value,select_items回溯与分支界限
回溯（全局搜索）逐步构造方案来找到所有解
首先选择一个决策，直到找到最终的解或者无法前进，无法前进返回上一层，继续下一个决策。
关键：剪枝（避免重复）
分支界限（局部搜索找到最优解）逐步将空间缩小来找到问题的最优解。
根据规则生成一组候选解，对这组解评估，选出一个最优解，再根据最优解生成下一组，知道找到最终解
关键：剪枝（避免重复）
01背包中，回溯法：可以用于找到所有可能的解。分支界限：用于找到最优的解。
回溯法
def bag01(c,n,weight,value):
def back(i,c_weight,c_value):
'''
i : 第i件物品
c_weight：当前背包重量
c_value：当前背包价值
'''
nonlocal max_value
if c_weight > c:
return
if c_value > max_value:
max_value = c_value
if i == n:
return
# 不选第i件物品
back(i+1,c_weight,c_value)
# 选第i件物品
back(i+1,c_weight+weight[i],c_value+value[i])
max_value = 0
back(0,0,0)
return max_value
分支界限(对回溯算法的改进。剪枝)
def bag01(c,n,weight,value)：
# 创建一个节点类，保存当前状态和状态的价值上界。
class Node:
def __init__(self,level,value,weight):
# level表示当前节点的深度
self.level = level
self.value = value
self.weight = weight
# 定义对象之间的＜比较。
def __lt__(self,other):
return self.value > other.value
# 创建一个优先队列，用来保存待扩展的节点，初始队列只有一个节点，表示当前状态为空
nodes = [Node(0,0,0)]
max_value = 0
while nodes:
node = nodes.pop(0)
# 代表选完了所有的节点
if node.level == n:
if node_value > max_value:
max_value = node_value
continue
# bound 存储计算得到的价值上界
bound = node_value
# 不选第i件物品
for j in range(node.level,n):
# 装不下
if node.weight + weight[j] > c:
# 取物品的部分
bound += (c - node.weight) / weight[j] * value[j]
break
bound += value[j]
# 价值上界大于已知的最大价值
if bound > max_value:
nodes.append(Node(node.level+1,node.value,node.weight))
# 选第i件物品
bound = node.value + value[node.level]
weight = node.weight + weight[node.level]
if weight <= c and bound > max_value:
max_value = bound
if bound > max_value:
nodes.append(Node(node.level+1,bound,weight))
return max_value
