首页 > 代码库 > 【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 F - Piggy-Bank 【完全背包问题】
【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 F - Piggy-Bank 【完全背包问题】
https://vjudge.net/contest/68966#problem/F
http://blog.csdn.net/libin56842/article/details/9048173
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<cmath> 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 const int maxn=1e4+10; 10 int dp[maxn]; 11 int weight[505]; 12 int money[505]; 13 int main() 14 { 15 int T; 16 scanf("%d",&T); 17 while(T--) 18 { 19 // memset(dp,0,sizeof(dp)); 20 int E,F; 21 scanf("%d%d",&E,&F); 22 int v=F-E; 23 for(int i=0;i<=v;i++) 24 { 25 dp[i]=INF; 26 } 27 dp[0]=0; 28 int n; 29 scanf("%d",&n); 30 for(int i=1;i<=n;i++) 31 { 32 scanf("%d%d",&money[i],&weight[i]); 33 } 34 for(int i=1;i<=n;i++) 35 { 36 for(int k=weight[i];k<=v;k++) 37 { 38 dp[k]=min(dp[k],dp[k-weight[i]]+money[i]); 39 } 40 } 41 if(dp[v]<INF) 42 { 43 printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]); 44 } 45 else 46 { 47 printf("This is impossible.\n"); 48 } 49 50 } 51 return 0; 52 }
【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 F - Piggy-Bank 【完全背包问题】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。