国家重大建设项目库网站电话,一站式织梦网站模板,网站子目录绑定二级域名,青岛做网站的公司哪家好题目描述实现一个算法求解完全背包问题。完全背包问题的介绍如下#xff1a;已知一个容量为 totalweight 的背包#xff0c;有不同重量不同价值的物品#xff0c;问怎样在背包容量限制下达到利益最大化。完全背包问题的每个物品可以无限选用背包问题求解方法的介绍如下…题目描述实现一个算法求解完全背包问题。完全背包问题的介绍如下已知一个容量为 totalweight 的背包有不同重量不同价值的物品问怎样在背包容量限制下达到利益最大化。完全背包问题的每个物品可以无限选用背包问题求解方法的介绍如下用符号 Vi 表示第 i 个物品的价值Wi 表示第 i 个物品的体积Vi,j 表示当前背包容量为 j 时前 i 个物品最佳组合对应的价值。对于当前第 i 个商品如果包的容量能够装下该物品即 Wi≤j。此时需要判断装或者不装这个物品的价值对比选择使价值更大的情况即 Vi,jmax(ViVi−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]*(T1)
for i in range(N):for j in range(W[i], T1):dp[j] max(dp[j], dp[j-W[i]]V[i])
print(dp[-1])
