动态规划(二)HDU1114
2024-09-20 10:35:37
1.题目来源HDU1114
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.
2.题目分析
题目首先给定一个空存钱罐的重量和这个存钱罐最多能装进去的重量,现在需要在不打破这个存钱罐的情况下猜测里面最少的钱。每种钱的数量不做限制,条件是必须装满,同时给出每种钱币的价值和重量。
参考背包九讲,这属于完全背包问题,初始状态为装满的情况,所以放钱币的策略就变成了放几个问题,有的钱币组合不合理就设置得比较大。
3.代码如下
#include<iostream>
#include<algorithm>
using namespace std;
const int num = 10005;
const int abc = 9999999999;
int main(void)
{
//(1 <= P <= 50000, 1 <= W <= 10000)
//1 <= E <= F <= 10000, N (1 <= N <= 500)(coins)
int dp[num], C[num], W[num], T, N, E, F, V, i, j;
cin >> T;
while (T-- > 0) {
cin >> E >> F; // the weight of an empty pig and of the pig filled with coins
cin >> N; //the number of various coins used in the given currency.
V = F - E; //the rest of the space
//C is the value of the coin in monetary units, W is it's weight in grams.
for (i = 1; i <= N; i++)
cin >> W[i] >> C[i];
dp[0] = 0;
for (i = 1; i <= V; i++) dp[i] = abc;
for (i = 1; i <= N; i++) {
for (j = C[i]; j <= V; j++) {
dp[j] = min(dp[j], dp[j - C[i]] + W[i]);
}
}
if (dp[V] == abc) cout << "This is impossible."<<endl;
else cout << "The minimum amount of money in the piggy-bank is "<<dp[V]<<"."<<endl;
}
return 0;
}
最新文章
- 前后端分离开发——模拟数据mock.js
- [xcode]instruments来检验你的app
- 删除Ngnix 日志
- ajax对一些没有接口的数据进行分析和添加方法
- Winform将网页生成图片
- ENOVIA 基础
- 黑马程序猿——java基金会--jdk、变量
- BroadcastReceiver.PendingResult类别
- java中List接口的实现类 ArrayList,LinkedList,Vector 的区别 list实现类源码分析
- NPOI 操作excel之 将图片插入到指定位置;
- split-brain 脑裂问题(Keepalived)
- [skill][c][ld][gcc] 明确指定gcc在链接时明确使用静态库
- Go sql语句引号问题
- 【node】---socket---网络通信---【巷子】
- Python学习 :面向对象 -- 三大特性
- hdu1428(记忆化搜索)
- 四,Smarty模板技术/引擎-----内建函数
- STL源码剖析(容器适配器)
- http://blog.csdn.net/gobitan/article/details/1809763
- javascript--事件对象e的来源、意义、应用及其属性的用法 function(e){}