HDU 1114 Piggy-Bank(完全背包)
2024-08-24 11:28:57
题目链接: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 ;
}
最新文章
- Linux Shell 重定向与管道【转帖】
- code project 上的内存管理的示例代码
- webpack练手项目之easySlide(一):初探webpack (转)
- selenium杀掉浏览器进程方法
- [Android]通过js方法回调部分native报错 Web Console: Uncaught TypeError: Object [object Object] has no method &#39;xxx&#39;
- 脊柱外科病人资料管理系统的界面设计分析(2)--JOA评分记录的实现
- oracle的散列聚簇表
- 利用Velocity结合Spring发email
- IIS 发布后文件拒绝访问
- Java IntelliJ IDEA 不能显示项目里的文件结构解决办法
- QT5程序发布dll依赖
- Excel生成guid、uuid
- Linux 常用指令整理
- nuxt 2
- Python 日常技巧
- C++ Primer 笔记——标准库类型string
- java学习之路--集合基础之List和Set部分
- 人工智能为什么选择Python语言?
- c/c++ 整形转字符串
- Oracle简易界面工具 (Oracle 10g, Oracle 11g)
热门文章
- ASP.NET (HttpModule,HttpHandler)
- 2013 ACM区域赛长沙 A Alice’s Print Service HDU 4791
- [LeetCode] 3. Longest Substring Without Repeating Characters 解题思路
- Codeforces 296C Greg and Array
- oracle 语句优化
- SqlCommand对象
- nginx日志格式含义
- JavaScript- 省市联动代码
- 博客搬家到 http://fresky.github.io/ - Visual Studio的插件Pdbproj可以把pdb转换成C++项目
- js弹出层插件 -- weebox