首页 > 代码库 > 多重背包
多重背包
<span style="color:#3333ff;">/* __________________________________________________________________________________________________ * copyright: Grant Yuan * * algorithm: 多重背包 * * time : 2014.7.18 * *_________________________________________________________________________________________________* C - 部分背包 基础 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Description 急!灾区的食物依旧短缺。 为了拯救灾区同胞的生命。心系灾区同胞的你准备自己採购一些粮食支援灾区。如今如果你一共同拥有资金n元,而市场有m种大米,每种大米都是袋装产品。其价格不等,而且仅仅能整袋购买。请问:你用有限的资金最多能採购多少公斤粮食呢? 后记: 人生是一个充满了变数的生命过程。天灾、人祸、病痛是我们生命历程中不可预知的威胁。 月有阴晴圆缺。人有旦夕祸福,未来对于我们而言是一个未知数。那么。我们要做的就应该是珍惜如今,感恩生活―― 感谢父母,他们给予我们生命,抚养我们成人; 感谢老师,他们授给我们知识,教我们做人 感谢朋友,他们让我们感受到世界的温暖; 感谢对手,他们令我们不断进取、努力。 相同,我们也要感谢痛苦与艰辛带给我们的財富~ Input 输入数据首先包括一个正整数C,表示有C组測试用例,每组測试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包括3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20)。分别表示每袋的价格、每袋的重量以及相应种类大米的袋数。 Output 对于每组測试数据,请输出能够购买大米的最多重量。你能够如果经费买不光全部的大米,而且经费你能够不用完。每一个实例的输出占一行。 Sample Input 1 8 2 2 100 4 4 100 2 Sample Output 400 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<functional> #include<queue> #include<stack> #include<cstdlib> using namespace std; int sum,n,t; int p[105],w[105],f[105]; int dp[106][106]; int main() { cin>>t; while(t--){ cin>>sum>>n; for(int i=0;i<n;i++) cin>>p[i]>>w[i]>>f[i]; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=0;j<=sum;j++) for(int k=0;k<=f[i]&&k*p[i]<=j;k++) { dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*p[i]]+k*w[i]); //cout<<dp[(i+1)&1][j]<<endl; //system("pause"); } cout<<dp[n][sum]<<endl;} return 0; } </span>
多重背包