01背包问题(dp)_01背包问题测试数据

作者：weixin_40725706 | 2024-03-29 01:42:27

踩

01背包问题测试数据

题目描述
已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi，价值为Pi。那么，采用怎样的装包方法才会使装入背包物品的总价值最大。

输入
包含多组测试数据。第一行为一个整数T(1<=T<=10)，代表测试数据个数。

接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。（注意：结果可能超过int范围）

输出
对每组测试数据，输出其对应的所装物品的最大价值。

样例输入
1
10 5
2 6
2 3
6 5
5 4
4 6
样例输出
15
dp[i]=max(dp[i-wi]+pi,dp[i])

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll v1
2
3

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/332920