首页 > 代码库 > hdu1114 Piggy-Bank （DP基础 完全背包）
hdu1114 Piggy-Bank （DP基础 完全背包）
链接：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 __int6411 #define usint unsigned int12 #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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。