Piggy-Bank--hdu1114(完全背包)
http://acm.hdu.edu.cn/showproblem.php?pid=1114
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
The minimum amount of money in the piggy-bank is 100.
This is impossible.
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h> using namespace std; #define INF 0xfffffff
#define N 55000
int dp[N];
int main()
{
int T,s,e,m,t,w[N],v[N];
scanf("%d",&T);
while(T--)
{
memset(w,,sizeof(w));
memset(v,,sizeof(v));
scanf("%d %d",&s,&e);
m=e-s;
for(int i=;i<=m;i++)
dp[i]=INF;
scanf("%d",&t);
for(int i=;i<=t;i++)
{
scanf("%d %d",&w[i],&v[i]);
}
for(int i=;i<=t;i++)
{
for(int j=v[i];j<=m;j++)
{
if(dp[j]>dp[j-v[i]]+w[i])
dp[j]=dp[j-v[i]]+w[i];
}
}
if(dp[m]==INF)
printf("This is impossible.\n");
else
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);
}
return ;
}
最新文章
- 初识Spring
- JavaBean简单示例
- Mysql时间戳函数
- java file的一些方法
- shopex用户登陆错误提示在nginx下乱码问题
- OpenStack:安装Horizon
- RHCS集群
- Python import / pyd / dll
- Android GridView增加HeaderView和FooterView的实现
- 轻量化ViewControllers,读文章做的总结
- 201521123081《Java程序设计》 第9周学习总结
- Opticks依赖库的下载和编译
- C++异常处理 - 栈解旋,异常接口声明,异常类型和异常变量的生命周期
- 2018-2019-2 网络对抗技术 20165321 Exp5 MSF基础应用
- vue-router 中踏过的坑
- JAVA基础1---Object类解析
- async和await学习笔记
- Cent OS 常用命令搜集
- 实现ListView的加载更多的效果,如何将按钮布局到始终在ListView的最后一行
- systemtap 探针定制
热门文章
- /usr/bin/install -c -m 644 sample-config/httpd.conf /etc/httpd/conf.d/nagios.conf
- ubuntu下php-fpm多实例运行配置
- Sql Server RowNumber和表变量分页性能优化小计
- 【算法】最长回文子串 longest palindrome substring
- centos7 系统安全加固方案
- [模板] 动态ST表
- vue 指令---气泡提示(手撸实战)
- win7下qt error: undefined reference to `_imp__getnameinfo@28&#39;解决
- CSS3---关于背景
- 前端基础之CSS_2