Serendipity

山有木兮木有枝

0%

0-1背包问题

发表于 更新于 分类于

0-1背包问题

有n个重量和价值分别为wi、vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

穷竭搜索（DFS+递归）

其实这就像深度优先遍历搜索一样，每件物品有两种状态–拿或不拿，确定每个物品的状态转移函数如下：

f(i,j),表示从第i件物品挑选出总重量不超过j的物品的最大和价值

f(i,j) = f(i+1,j) (j<w[i] 第i件物品重量大于剩余重量，表示不能选取此物品）
max(f(i+1,j),f(i+1,j-w[i])+v[i]) （此物品可选，但是否选取由谁的价值大决定）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
def record(i,j):
    res = 0
    if i == n:
        res = 0
    elif j < w[i]:
        res = record(i+1,j)
    else:
        res = max(record(i+1,j),record(i+1,j-w[i])+v[i])
    return res
print(record(0,W))

不足：通过画深度优先遍历的图来看可以发现有重复计算的值，最坏需要O(2^n^)的时间

记忆化搜索

在进行DFS遍历每个数的时用一个二维列表记录，下次遇到同样的数字即可直接调用，只需O(n*w)的复杂度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
d = [[-1 for i in range(W+1)] for j in range(n+1)] #-1表示标记
def record(i,j):
    res = 0
    if d[i][j] >= 0:
        return d[i][j]
    elif i == n:
        res = 0
    elif j < w[i]:
        res = record(i+1,j)
    else:
        res = max(record(i+1,j),record(i+1,j-w[i])+v[i])
    d[i][j] = res
    return d[i][j]
print(record(0,W))

动态规划

二维列表dp根据状态转移函数的定义可以变化成如下递推公式：

dp[n][j]= 0

dp[i][j] = dp[i+1][j] (j<w[i])

max(dp[i+1][j]+ dp[i+1][j-w[i]]+v[i]) 其他

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [[-1 for i in range(W+1)] for j in range(n+1)]
#初始化dp[n][j] = 0
for index in range(W+1):
    dp[n][index] = 0
def DP():
    i = n-1
    while i >= 0:
        for j in range(W+1):
            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[i][j])
        i -= 1
    print(dp[0][W])
DP()

正向递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
正向递推，上面的方法是逆推的，dp[i+1][j] = 从前i个物品中挑选出总重量不超过j的物品的价值和的最大值
'''
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [[-1 for i in range(W+1)] for j in range(n+1)]
for index in range(W+1):
    dp[0][index] = 0
def DP():
    i = 0
    while i < n:
        for j in range(W+1):
            if j < w[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
        i += 1
    print(dp[n][W])
DP()

改进:dp数组再利用

改进，0-1背包问题只用一个数组完成，与上面的只是J控制时遍历的方向不同

1
2
3
4
5
6
7
8
9
10
11
12
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [0]*(n*W)
def DP():
    for i in range(n):
        j = W
        while j >= w[i]:
            dp[j] = max(dp[j],dp[j - w[i]] + v[i])
            j -= 1
    print(dp[W])
DP()