01背包问题基本可以用一句话描述，i件物品中挑选若干不重复放入容量V的背包中，使得价值最大
核心转移方程为
F[i][v] = max(F[i-1][v],F[i − 1, v − Wi] + Ci)
方程就一个意思，i件物品的最大价值，可以划分为 i-1件物品的最大价值，再放一件物品 或者 不再放物品
基本实现用递归即可，初始化第1行即可，第0行与第0列肯定是0
需要关注的点：
1、查找下标初始化必须为-1，用于区分合法码与非法码
2、每次需要关注-容量允许下的最大价值[同时没有被使用过]，因此，容量每次需要判断是否大于0，且没有被使用过
3、下标记录集合，最后必须要用set进行去重
import sys
count=0
param = {}
inputData = []
for line in sys.stdin:
single = line.strip().split(" ")
if count==0:
param["N"] = int(single[0])
param["V"] = int(single[1])
pass
elif count<=int(param["N"]):
item = {}
item["C"] = int(single[0])
item["W"] = int(single[1])
inputData.append(item)
pass
else:
break
count+=1
pass
# 初始化查询保存的表 i*V 的表 每一行代表几个物品的最大价值 每一列代表容量上限不同的最大价值
F = [[0 for j in range(param["V"]+1)] for i in range(param["N"]+1)]
def getMaxOne(v:int,initList:list[dict],already:list[int])->list[int]:
'''
从原始数据中捞出背包容量允许下的最大价值[同时没有被使用过]
:param v: 背包容量
:param initList: 输入原始数据
:param already: 已经使用过的下标
:return:找到的最大价值物品的下标
'''
# 初始化状态必须是非法状态 这样才能拿分辨是否找到对应下标
# 否则区分不出 下标为0与没有找到两种情况
maxValue = 0
maxIndex = -1
if v>0:
for i in range(len(initList)):
item = initList[i]
if i not in already and item["W"]<=v:
if item["C"]>maxValue:
maxValue = item["C"]
maxIndex = i
pass
pass
pass
if maxValue>0:
F[1][v] = maxValue
pass
pass
return [maxIndex]
def calculateF(i:int,v:int,initList:list[dict],alreadyInput:list[int])->list[int]:
'''
通过递归找 i 件物品 V 容量下的最大价值
:param i: i 件物品
:param v: v 容量
:param initList: 原始数组,递归过程中保持不变 仅already数组该改变识别是哪些物品组成的结果
:param already: 已经使用过的物品
:return:最大价值对应的物品下标
'''
if i==1:
return getMaxOne(v,initList,alreadyInput)
else:
# F[i-1][v]
alreadyBefore = calculateF(i-1,v,initList,alreadyInput)
maxValue = F[i-1][v]
alreadyOut = alreadyBefore
# F[i − 1, v − Wi] + Ci
'''
剔除掉上一层递归使用过的物品
然后，逐个物品进行尝试v-w的最大价值与该物品的相加
与F[i-1][v]比较 如果更大 则更新 maxValue 从而得到F[i][v]
'''
for iterNum in range(len(initList)):
if iterNum in alreadyInput:
continue
else:
item = initList[iterNum]
alreadyTemp = [iterNum]
alreadyTemp.extend(alreadyInput)
alreadyAfter = calculateF(i - 1, v - item["W"], initList, alreadyTemp)
if -1 in alreadyAfter:
continue
maxValueTemp = F[i - 1][v - item["W"]] + item["C"]
alreadyAfter.append(iterNum)
if maxValueTemp > maxValue:
maxValue = maxValueTemp
alreadyOut = alreadyAfter
pass
pass
F[i][v] = maxValue
alreadyOut.extend(alreadyInput)
return alreadyOut
pass
already = calculateF(param["N"],param["V"],inputData,[])
print(F[-1][-1])