求解完全背包问题

题目描述

实现一个算法求解完全背包问题。完全背包问题的介绍如下：

• 已知一个容量为 totalweight 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。

• 完全背包问题的每个物品可以无限选用

背包问题求解方法的介绍如下：

• 用符号 Vi 表示第 i 个物品的价值，Wi 表示第 i 个物品的体积，Vi,j 表示当前背包容量为 j 时，前 i 个物品最佳组合对应的价值。

• 对于当前第 i 个商品，如果包的容量能够装下该物品，即 Wi≤j。此时需要判断装或者不装这个物品的价值对比，选择使价值更大的情况，即 Vi,j=max(Vi+Vi−1,j−Wi,Vi−1,j)

输入描述

第一行为两个数字 otalweight、N，均不超过 1000。totalweight 含义见题干，N 为物品数量。

接下来 N 行，每行两个数字 Wi、Vi，均不超过 1000。含义见题干。

输出描述

输出一行，为在背包容量限制下的最大化利益。

输入输出样例

示例

输入

8 5
3 4
5 5
1 2
2 1
2 3

输出

16

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

参考答案

T,N = map(int, input().split())
W = []
V = []
for _ in range(N):a,b = map(int, input().split())W.append(a)V.append(b)
dp = [0]*(T+1)
for i in range(N):for j in range(W[i], T+1):dp[j] = max(dp[j], dp[j-W[i]]+V[i])
print(dp[-1])