题目链接: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.
 
分析:这道题目的动态规划思想很简单,就是背包。
  
代码如下:
 # include<stdio.h>
# include<string.h>
const int N = ;
const int INF = 0xffffff;
int f[]; //f[i]表示总重量为i的硬币,价值为多少
int p[N],w[N];
int main()
{
int T;
scanf("%d",&T);
while (T--){
int n,a,b,i,j;
scanf("%d%d",&a,&b);
f[] = ; //表示重量为0的硬币价值为0
for (i=;i<=b;i++) f[i]=INF;
scanf("%d",&n);
for (i=;i<=n;i++) scanf("%d%d",&p[i],&w[i]);
for (i=;i<=n;i++){
for (j=w[i];j<=b-a;j++){
if (f[j-w[i]]+p[i]<f[j]) f[j]=f[j-w[i]]+p[i];
}
}
if (f[b-a]==INF) printf("This is impossible.\n");
else printf("The minimum amount of money in the piggy-bank is %d.\n",f[b-a]);
}
return ;
}

最新文章

  1. Linux Shell 重定向与管道【转帖】
  2. code project 上的内存管理的示例代码
  3. webpack练手项目之easySlide(一):初探webpack (转)
  4. selenium杀掉浏览器进程方法
  5. [Android]通过js方法回调部分native报错 Web Console: Uncaught TypeError: Object [object Object] has no method &#39;xxx&#39;
  6. 脊柱外科病人资料管理系统的界面设计分析(2)--JOA评分记录的实现
  7. oracle的散列聚簇表
  8. 利用Velocity结合Spring发email
  9. IIS 发布后文件拒绝访问
  10. Java IntelliJ IDEA 不能显示项目里的文件结构解决办法
  11. QT5程序发布dll依赖
  12. Excel生成guid、uuid
  13. Linux 常用指令整理
  14. nuxt 2
  15. Python 日常技巧
  16. C++ Primer 笔记——标准库类型string
  17. java学习之路--集合基础之List和Set部分
  18. 人工智能为什么选择Python语言?
  19. c/c++ 整形转字符串
  20. Oracle简易界面工具 (Oracle 10g, Oracle 11g)

热门文章

  1. ASP.NET (HttpModule,HttpHandler)
  2. 2013 ACM区域赛长沙 A Alice’s Print Service HDU 4791
  3. [LeetCode] 3. Longest Substring Without Repeating Characters 解题思路
  4. Codeforces 296C Greg and Array
  5. oracle 语句优化
  6. SqlCommand对象
  7. nginx日志格式含义
  8. JavaScript- 省市联动代码
  9. 博客搬家到 http://fresky.github.io/ - Visual Studio的插件Pdbproj可以把pdb转换成C++项目
  10. js弹出层插件 -- weebox