首页 > 代码库 > hdu 1114 完全背包问题

hdu 1114 完全背包问题

题意:给定背包体积与物品的体积与价值 求正好放完的最小价值
#include<iostream> using namespace std; int min(int a,int b) { if(a<b) return a; return b; } int main() { int t,m1,m2,n,i,j; int v[502],w[502],dp[10005],m; cin>>t; while(t--) { cin>>m1>>m2; m=m2-m1; cin>>n; for(i=1;i<=n;i++) cin>>v[i]>>w[i]; for(i=1;i<=m;i++) dp[i]=-2000000000; dp[0]=0; for(i=1;i<=n;i++) for(j=w[i];j<=m;j++) if(dp[j]<0) dp[j]=dp[j-w[i]]+v[i];//j个容量能装下的最小值是 能装下w[i]重量的值+j-w[i]能装下的最小值 else if(dp[j-w[i]]+v[i]>0) dp[j]=min(dp[j],dp[j-w[i]]+v[i]);//j-w[i]是上一为状态 if(dp[m]>0) cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }