多重背包 Ⅰ 0/1背包问题 空间优化 Python

本文主要是介绍多重背包 Ⅰ 0/1背包问题 空间优化 Python，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目在AcWing里：4. 多重背包问题 I - AcWing题库 

这题用0/1背包问题的思路可以做，把多个物品逐一枚举。

那么空间优化的逻辑便是：

既然当前物品的体积小于等于枚举的背包体积时状态转移方程是：

ans[ i ][ j ] = max(ans[ i - 1 ][ j ] , value[ i ] + arr[ i - 1 ][ j - value[ i ]]) 

i 表示的是当前行 ，i - 1 表示的是上一行数据

j 表示的是当前列，同时也是枚举到的当前考虑的背包体积。

发现：整个式子只需要考虑两行数据：当前行和上一行，那么原来的思路就会浪费许多不必要的空间（不信自己列图模拟）。

那么再根据取模知识，设取模数为 mod ,取模后的结果只有0 - mod-1之间的循环，把 mod 值定为 2 ，那么便只有0，1，0，1，0，1 ......，如果 i % 2 表示当前行，那么 ( i + 1 ) % 2表示的就会是上一行。 

n,bag = map(int,input().split())
arr = []
all = 0
for _ in range(n):
    a,b,c = map(int,input().split())
    all += c
    while c:
        c-=1
        arr.append([a,b])
new = [[0 for _ in range(bag+1)] for i in range(2)]
for i in range(all):
    get_new = new[(i+1)%2]
    lastNew = new[i%2]
    get_arr = arr[i]
    for j in range(1,bag+1):
        if get_arr[0] > j:get_new[j] = lastNew[j]
        else:get_new[j] = max(lastNew[j],get_arr[1]+lastNew[j-get_arr[0]])
print(new[all%2][-1])

这篇关于多重背包 Ⅰ 0/1背包问题 空间优化 Python的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！