0-1 背包 不可分割

有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

1. 用v[i]表示物品价值，w[i]表示物品重量。定义状态dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值。
2. 初始化边界条件，V(0,j)=V(i,0)=0；
3. 对于每一个物品，有两种选择方法，能装下和不能装下。
第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；
因此：

① j<w(i)      V(i,j)=V(i-1,j)            //只是为了好理解，可以不用写，不会影响结果。

② j>=w(i)     V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝ 


number, capacity = 4, 8
w = [0, 2, 3, 4, 5]
v = [0, 3, 4, 5, 6]
dp = [[0] * (capacity + 1) for _ in range(number + 1)]
for i in range(number + 1):
    for j in range(capacity + 1):
        if i == 0:
            dp[i][j] = 0
        elif j == 0:
            dp[i][j] = 0
        else:
            if j < w[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i])

print(dp)
print(dp[number][capacity])


完全背包问题

有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。
每个物品有无限个 
number, capacity = 3, 5
w = [0, 3, 2, 2]
v = [0, 5, 10, 20]
dp = [[0] * (capacity + 1) for _ in range(number + 1)]
for i in range(number + 1):
    for j in range(capacity + 1):
        if i == 0:
            dp[i][j] = 0
        elif j == 0:
            dp[i][j] = 0
        else:
            nCount = j // w[i]
            for k in range(nCount + 1):
                dp[i][j] = max(dp[i][j], dp[i-1][j - k*w[i]] + k * v[i])

print(dp)
print(dp[number][capacity])


背包问题可分割 



m = eval(input('可承载的最大重量：'))
h = eval(input('宝物重量：'))
v = eval(input('宝物价值：'))
 
# 计算权重, 整合得到一个数组
arr = [(i,v[i]/h[i], h[i], v[i]) for i in range(len(h))]
 
# 按照list中的权重，从大到小排序
arr.sort(key=lambda x:x[1], reverse=True)  # list.sort() list排序函数
 
bagVal = 0
bagList = []
for i,w,h,v in arr:
    # 1 如果能放的下宝物，那就把宝物全放进去
    if w <= m:
        m -= h
        bagVal += v
        bagList.append(i)
    
    # 2 如果宝物不能完全放下，考虑放入部分宝物
    else:
        bagVal += m * w
        bagList.append(i)
        break
 
print('\n排序后：',arr)
print('能运走的最大价值：%.2f'%bagVal,'此时承载的宝物有：',bagList)