题目:
特大背包问题 (20分)
C时间限制:1000 毫秒 | C内存限制:10000 Kb
题目内容:
现在有一个容量为C的背包和N个重量和价值已知的物品. 现在要从这n个物品中挑选出一些物品, 使得选择的物品的总重量不超过背包的容量, 且总价值最大.
此题的数据范围:
1 <= C <= 10^8(10的8次方)
1 <= N <= 100
输入描述
有多组测试数据. 第一行一个正整数T(T<=15), 表示测试数据组数.
对于每组测试数据:
第一行两个正整数N和C, 分别表示物品的数量和背包的容量.
接下来N行, 每行两个正整数w,v ,分别表示对应物品的重量和价值(1<= w <= 10^7, 1<= v <= 100)
输出描述
输出一个正整数, 表示在所选物品不超过背包容量的情况下, 能够得到的最大价值.
输入样例
1
3 10
5 10
5 10
4 12
输出样例
22
————————————————
思路:
先求出所有物品的总价值V, 用一个一维数组,下标对应价值,数组储存总价值依次减小时需要的最小容量,。
最后输出 题目所给背包容量对应的价值即为所求答案。
核心代码:
for(i=1;i<=n;i++)for(int j = V ;j >= v[i];j--)dp[j]= min( dp[j] , dp[j-v[i]] + w [i]);
#include <iostream>
#include<cstring>
using namespace std;
long long int w[10000],v[10000],dp[10000];
int main()
{int t;cin>>t;while(t--){long long int i,j,n,c,V=0;cin>>n>>c;for(i=1;i<=n;i++) {cin>>w[i];cin>>v[i];V+=v[i];}memset(dp,1000000010,sizeof(dp)); ///要求最小容量,初始化为最大值;dp[0]=0;for(i=1;i<=n;i++)for(int j = V ;j >= v[i];j--)dp[j]= min( dp[j] , dp[j-v[i]] + w [i]);for( i=V ;i>=0 ; i--)if(dp[i]<=c){cout<<i<<endl; ///此处输出i,即为满足条件的最大价值break;}}return 0;
}
参考文献:
https://www.cnblogs.com/kkbill/p/12081172.html
http://www.mamicode.com/info-detail-2974086.html
https://www.cnblogs.com/young-children/p/11742279.html
https://blog.csdn.net/De_lovely_crane/article/details/100829699
https://blog.csdn.net/nameofcsdn/article/details/106630159
https://blog.csdn.net/nameofcsdn/article/details/107235360