01背包问题（动态规划）python dp二维数组_numpy实现二维背包问题

01背包问题（动态规划）

题目链接

造不出轮子，研究一下背包问题经典算法 dp数组，这是链接。看完大概能试着写写代码了。

1.读取输入并创建dp数组

import numpy as np
n, v = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)]
dp = np.zeros((4, 5))
1
2
3
4

2.初始化二维dp数组

for i in range(n):
    dp[i][0] = 0
for i in range(1, v+1):
    if item[0][0] <= i:
        dp[0][i] = item[0][1]
1
2
3
4
5

3.填充dp数组并输出

for i in range(1, n):
    for j in range(1, v+1):
        if j < item[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
print(dp[n-1][v])
1
2
3
4
5
6
7

4.优化思路

链接中有用一维dp数组的办法，还没来得及看。一维dp数组还能进一步优化迭代顺序，太TM高级了。

5.全部代码

def zeros(m, n):
    output = [[] for i in range(m)]
    for i in range(m):
        for j in range(n):
            output[i].append(0)
    return output

n, v = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)] #item[i][0]是物品体积，item[i][1]是物品价值
dp = zeros(n, v+1)

'''初始化dp二维数组'''
for i in range(n):
    dp[i][0] = 0
for i in range(1, v+1):
    if item[0][0] <= i:
        dp[0][i] = item[0][1]
        
for i in range(1, n):
    for j in range(1, v+1):
        if j < item[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
print(dp[n-1][v])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25