问题描述：给定n种物品和一背包。物品i的重量是wi，体积是bi,其价值为vi，背包的容量为C，容积为D。问：应该如何选择装入背包种的物品，使得总价值最大？
其实，这就是一维0-1背包问题的推广，二维背包问题，只要我们把二维背包问题解决了，n维背包问题也就解决了。
二维背包问题，只不过是多加了一个体积的限制条件，那么在纬度上我们需要多加一个纬度，用来衡量体积，具体代码如下：
w = [3, 2, 4]
b = [2, 4, 3]
v = [3, 2, 5]
w_most = 7
b_most = 7
def bag_0_1(w, b, v, w_most, b_most):
bag_num = len(w)
w.insert(0, 0)
b.insert(0, 0)
v.insert(0, 0)
dp_table = np.zeros((bag_num+1, w_most+1, b_most+1), np.int)
for i in range(1, bag_num+1):
for j in range(1, w_most+1):
for k in range(1, b_most+1):
if w[i] <= j and b[i] <= k:
dp_table[i][j][k] = max(dp_table[i-1][j][k], dp_table[i-1][j-w[i]][k-b[i]] + v[i])
else:
dp_table[i][j][k] = dp_table[i-1][j][k]
return dp_table
a = bag_0_1(w, b, v, w_most, b_most)
print(a)
print(a.max())
结果如下：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84735.html
