链接:Piggy-Bank
大意:已知一只猪存钱罐空的时候的重量、现在的重量,已知若干种钱的重量和价值,猪里面装着若干钱若干份,求猪中的钱的价值最小值。
题解:
DP,完全背包。
g[j]表示组成重量j的最小花费
g[j]=min(g[j],g[j-w[i]]+v[i])
完全背包物品可以多次使用,所以j的循环要正着来。
代码:
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 using namespace std; 10 #define ll __int64 11 #define usint unsigned int 12 #define mz(array) memset(array, 0, sizeof(array)) 13 #define minf(array) memset(array, inf, sizeof(array)) 14 #define REP(i,n) for(int i=0;i<(n);i++) 15 #define FOR(i,x,n) for(int i=(x);i<=(n);i++) 16 #define RE freopen("1.in","r",stdin) 17 #define WE freopen("1.out","w",stdout) 18 19 const int maxn=555; 20 const int maxv=10001; 21 const int inf=0x3f3f3f3f; 22 23 int w[maxn],v[maxn]; 24 int g[maxv]; 25 26 int main() { 27 int i,j,k,ans,t; 28 int e,f,n; 29 scanf("%d",&t); 30 while(t--) { 31 scanf("%d%d%d",&e,&f,&n); 32 for(i=0; i<n; i++) 33 scanf("%d%d",&v[i],&w[i]); 34 minf(g); 35 g[0]=0; 36 REP(i,n) 37 FOR(j,w[i],maxv-1) 38 g[j]=min(g[j],g[j-w[i]]+v[i]); 39 if(g[f-e]==inf) printf("This is impossible.\n"); 40 else printf("The minimum amount of money in the piggy-bank is %d.\n",g[f-e]); 41 } 42 return 0; 43 }
hdu1114 Piggy-Bank (DP基础 完全背包),布布扣,bubuko.com
hdu1114 Piggy-Bank (DP基础 完全背包)
原文:http://www.cnblogs.com/yuiffy/p/3885216.html