逃亡的准备(hallows)
【问题描述】
在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。
【输入文件】(hallows.in)
(1)第一行有2个整数,物品种数n和背包装载体积v。
(2)2行到i+1行每行3个整数,为第i种物品的数量m、体积w、价值s。.
【输出文件】(hallows.out)
输出文件hallows.out仅包含一个整数,即为能拿到的最大的物品价值总和。
【输入样例】
2 10
3 4 3
2 2 5
【输出样例】
13
【注释】
选第一种一个,第二种两个。
结果为3*1+5*2=13
【数据规模】
对于30%的数据
1<=v<=500
1<=n<=2000
1<=m<=10
1<=w<=20
1<=s<=100
对于100%的数据
1<=v<=500
1<=n<=2000
1<=m<=5000
1<=w<=20
1<=s<=100
#include<bits/stdc++.h> using namespace std; int dp[2000]; int n,v,vai[10000005],vi[10000005],nn; void make_dp(int i){ for(int j=v;j>=0;j--){ if(dp[j]!=-1){ if(dp[j+vi[i]]<dp[j]+vai[i]){ dp[j+vi[i]] = dp[j]+vai[i]; } } } return; } int main(){ memset(dp,-1,sizeof(dp)); dp[0]=0; cin>>n>>v; for(int i=0;i<n;i++){ cin>>nn>>vi[i]>>vai[i]; for(int j=i;j<i+nn;j++){ vi[j]=vi[i];vai[j]=vai[i]; make_dp(j); } i+=nn-1; n+=nn-1; }/* for(int i=0;i<n;i++){ cout<<i<<"\t"<<vi[i]<<"\t"<<vai[i]<<endl; } */ int ans=-1000; for(int i=v;i>=0;i--){ cout<<"dp["<<i<<"] = "<<dp[i]<<endl; if(dp[i]>ans){ ans=dp[i]; } } cout<<ans<<endl; return 0; }