首页 > 代码库 > poj 1384 Piggy-Bank （完全背包）
poj 1384 Piggy-Bank （完全背包）
http://poj.org/problem?id=1384
题意：给出一个储蓄罐 的空和满时的重量
再给出n种硬币的 value 和 weight
问满足正好装满罐子时的最小价值是多少
思路 ：
if(dp[j]>dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i];
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>using namespace std;int main(){ int e,f; int n,t; int i,j,k; int INF=1000000000; int v[1000],w[1000]; int dp[10000+100]; scanf("%d",&t); while(t--) { scanf("%d%d",&e,&f); f=f-e; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); for(i=1;i<=f;i++) dp[i]=INF; dp[0]=0; for(i=1;i<=n;i++) { for(j=w[i];j<=f;j++) { if(dp[j]>dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i]; } } if(dp[f]<INF) printf("The minimum amount of money in the piggy-bank is %d.\n",dp[f]); else printf("This is impossible.\n"); } return 0;}
poj 1384 Piggy-Bank （完全背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。