HDU 1114 Piggy-Bank(完全背包)
HDU 完全 背包
2023-09-14 08:58:23 时间
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114
题目大意:根据储钱罐的重量,求出里面钱最少有多少。给定储钱罐的初始重量,装硬币后重量,和每个对应面值硬币的重量。
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
分析:这道题目的动态规划思想很简单,就是背包。
代码如下:
1 # include<stdio.h> 2 # include<string.h> 3 const int N = 501; 4 const int INF = 0xffffff; 5 int f[10001]; //f[i]表示总重量为i的硬币,价值为多少 6 int p[N],w[N]; 7 int main() 8 { 9 int T; 10 scanf("%d",&T); 11 while (T--){ 12 int n,a,b,i,j; 13 scanf("%d%d",&a,&b); 14 f[0] = 0; //表示重量为0的硬币价值为0 15 for (i=1;i<=b;i++) f[i]=INF; 16 scanf("%d",&n); 17 for (i=1;i<=n;i++) scanf("%d%d",&p[i],&w[i]); 18 for (i=1;i<=n;i++){ 19 for (j=w[i];j<=b-a;j++){ 20 if (f[j-w[i]]+p[i]<f[j]) f[j]=f[j-w[i]]+p[i]; 21 } 22 } 23 if (f[b-a]==INF) printf("This is impossible.\n"); 24 else printf("The minimum amount of money in the piggy-bank is %d.\n",f[b-a]); 25 } 26 return 0; 27 }
相关文章
- hdu 1950 Bridging signals 求最长子序列 ( 二分模板 )
- HDU 1619 Unidirectional TSP(单向TSP + 路径打印)
- HDU 3006 The Number of set(位运算 状态压缩)
- 【47.92%】【hdu 5763】Another Meaning
- 【hdu 2897】邂逅明下
- 【hdu 4333】Revolving Digits
- hdu 4865 Peter's Hobby(2014 多校联合第一场 E)
- hdu 4775 Infinite Go(暴力)
- HDU 4521 小明系列问题——小明序列 (线段树维护DP)
- HDU 3304 Interesting Yang Yui Triangle lucas定理
- HDU 1030 Delta-wave 数学题解
- hdu 4849 最短路 西安邀请赛 Wow! Such City!
- Saving HDU hdu
- HDU-4879-ZCC loves march(map+set+并查集)
- HDU 1051 Wooden Sticks (贪心)