23421: 小偷背包

dp, http://cs101.openjudge.cn/practice/23421

这是《算法图解》[1]书中第9章动态规划的例子：一个小贼正在一家店里偷商品。

假设一种情况如下：

一个小偷背着一个可装 4 磅东西的背包。商场有三件物品分别为：价值 3000 美元重 4 磅的音响，价值 2000 美元重 3 磅的笔记本，价值1500美元重1磅的吉他。

问小偷应该怎样选择商品，才能使得偷取的价值最高？

输入

第一行是两个整数N和B，空格分隔。N表示物品件数，B表示背包最大承重。第二行是N个整数，空格分隔。表示各个物品价格。第三行是N个整数，空格分隔。表示各个物品重量（是与第二行物品对齐的）。

输出

输出一个整数。保证在满足背包容量的情况下，偷的价值最高。

样例输入

3 4
3000 2000 1500
4 3 1

样例输出

python

n,b=map(int, input().split())
price=[0]+[int(i) for i in input().split()]
weight=[0]+[int(i) for i in input().split()]
bag=[[0]*(b+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,b+1):
        if weight[i]<=j:
            bag[i][j]=max(price[i]+bag[i-1][j-weight[i]], bag[i-1][j])
        else:
            bag[i][j]=bag[i-1][j]
print(bag[-1][-1])

01-背包，滚动数组，https://oi-wiki.org/dp/knapsack/

python

N, B = map(int, input().split())
values = list(map(int, input().split()))
weights = list(map(int, input().split()))

dp = [0] * (B + 1)

for i in range(N):
    prev = dp[:]  # 复制上一次的状态
    for j in range(B + 1):
        if j >= weights[i]:
            dp[j] = max(prev[j], prev[j - weights[i]] + values[i])

print(dp[B])

python

# 压缩矩阵/滚动数组 方法
N,B = map(int, input().split())
*p, = map(int, input().split())
*w, = map(int, input().split())

dp=[0]*(B+1)
for i in range(N):
    for j in range(B, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j-w[i]]+p[i])
            
print(dp[-1])

递归的动态规划（Dynamic Programming, DP）解决方案，用于解决“小偷背包”问题。具体来说，这是一个 0-1 背包问题，目标是在不超过背包容量的情况下最大化所选物品的总价值。

python

import math


def fn(i, s):
  # i-th item, knapsack with available capacity s

  if (s < 0):
    return -math.inf
  if (i == len(v)):
      return 0

  return max(fn(i+1, s), v[i] + fn(i+1, s-w[i]))


N, B = map(int, input().split())
*v, = map(int, input().split())
*w, = map(int, input().split())
print(fn(0, B))

这个代码实现了一个递归的动态规划（Dynamic Programming, DP）解决方案，用于解决“小偷背包”问题。具体来说，这是一个 0-1 背包问题，目标是在不超过背包容量的情况下最大化所选物品的总价值。
i 表示当前考虑的物品索引。
s 表示当前背包的剩余容量。
基本情况：
如果 s < 0，表示当前选择的物品超出了背包容量，返回负无穷大 -math.inf，表示这种情况不可行。
如果 i == len(v)，表示所有物品都已经考虑完毕，返回 0，表示没有更多的物品可以选择。
递归情况：
fn(i+1, s) 表示不选择第 i 个物品的情况。
v[i] + fn(i+1, s-w[i]) 表示选择第 i 个物品的情况，此时背包容量减少 w[i]，价值增加 v[i]。
返回这两种情况中的最大值。
代码示例
假设输入为：
3 5
4 5 6
2 3 4
代码的执行过程如下：
初始化：
N = 3，B = 5
v = [4, 5, 6]
w = [2, 3, 4]
递归调用：
fn(0, 5)：
不选择第 0 个物品：fn(1, 5)
选择第 0 个物品：4 + fn(1, 3)
fn(1, 5)：
不选择第 1 个物品：fn(2, 5)
选择第 1 个物品：5 + fn(2, 2)
fn(2, 5)：
不选择第 2 个物品：fn(3, 5)
选择第 2 个物品：6 + fn(3, 1)
fn(3, 5) 和 fn(3, 1) 都返回 0，因为所有物品已经考虑完毕。
回溯计算：
fn(2, 5) = max(0, 6 + 0) = 6
fn(1, 5) = max(6, 5 + 6) = 11
fn(0, 5) = max(11, 4 + 6) = 11
最终输出：
11
总结
这个代码通过递归的方式解决了 0-1 背包问题，通过比较选择和不选择当前物品的情况，最终返回最大价值。递归过程中使用了负无穷大 -math.inf 来表示不可行的情况。

23421: 小偷背包 ​

23421: 小偷背包