蓝桥杯刷题第二天——背包问题
题目描述
有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi价值是Wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有N行，每行两个整数,W，用空格隔开，分别表示第件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0< N,V≤ 1000
0<v,W≤1000
解题思路
此题可用动态规划来解决。
1.首先定义一个二维数组组dp[i][j]，表示前i个物品放入容量为j的背包中能获得的最大价值。
2.状态转移方程为：dp[i][j]=max(dp[i－1][j]，dp[i－1][j－v[i]]+w[i]]，其中v[i] 和 w[i] 分别是第i个物品的体积和价值。这个方程的含义是，对于第i个物品，有两种选择：不放入背包（价值为dp[i－1][j]），或者放入背包（价值为dp[i－1][j－v[i]]+w[i]），取两者中的较大值。
3.边界条件：当i=或=时，dp[i][j］=，即没有物品或者背包容量为0时，最大价值为 0。
代码示例
N, V = map(int, input().split())
dp = [[0] * (V + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
v, w = map(int, input().split())
for j in range(1, V + 1):
dp[i][j] = dp[i - 1][j]
if j >= v:
dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w)
print(dp[N][V])结果展示
