首页 > 代码库 > hdu 2191
hdu 2191
额……杭电蹦了……就先这样吧……多重背包……
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<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; int n; int dp[110]; void zero(int w,int v) { int i; for(i=n;i>=w;i--) dp[i]=max(dp[i],dp[i-w]+v); } void cp(int w,int v) { int i; for(i=w;i<=n;i++) dp[i]=max(dp[i],dp[i-w]+v); } void mul(int pw,int pv,int num) { int t; if(num*pw>=n) cp(pw,pv); else { t=1; while(num>=t) { zero(t*pw,t*pv); num-=t; t<<=1; } if(num>0) zero(num*pw,num*pv); } } int main() { int T,m,p,h,c; cin>>T; while(T--) { cin>>n>>m; memset(dp,0,sizeof(dp)); while(m--) { cin>>p>>h>>c; mul(p,h,c); } cout<<dp[n]<<endl; } return 0; }
hdu 2191
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。