算法图解案例

代码求解

import numpy as np
commodities = np.array([[1500, 3000, 2000], [1, 4, 3]])  # 商品列表，第一行表示商品的价格，第二行表示商品的重量
arr = np.zeros((commodities.shape[1], 4), dtype=int)  # 动态规划表格
max_val = 0  # 能够偷取的商品的最大价值
# 先填充表格的第一行（即偷取第一个商品）
for j in range(0, arr.shape[1]):
    arr[0][j] = commodities[0][0] if commodities[1][0] <= j + 1 else 0
# 依次偷取剩余商品然后比较价格
for i in range(1, arr.shape[0]):
    for j in range(0, arr.shape[1]):
        if commodities[1][i] <= j + 1:
            left_space = j + 1 - commodities[1][i]
            before_val = arr[i - 1][j]
            current_val = commodities[0][i] if left_space == 0 else commodities[0][i] + arr[i - 1][left_space - 1]
            arr[i][j] = current_val if current_val > before_val else before_val
        else:
            arr[i][j] = arr[i - 1][j]
max_val = arr.flatten()[-1]  # 表格最后一个值为最后能够偷取的最大价值
print(arr)
print(max_val)