uva10465Homer Simposon(完全背包)
发布日期:2022-02-02 02:58:10 浏览次数:4 分类:技术文章

本文共 1709 字,大约阅读时间需要 5 分钟。


Problem C: Homer Simpson

Time Limit: 3 seconds
Memory Limit: 32 MB


Homer Simpson, a very smart guy, likes eating Krusty-burgers. It takes Homer m minutes to eat a Krusty- burger. However, there�s a new type of burger in Apu�s Kwik-e-Mart. Homer likes those too. It takes him n minutes to eat one of these burgers. Given t minutes, you have to find out the maximum number of burgers Homer can eat without wasting any time. If he must waste time, he can have beer.

Input

Input consists of several test cases. Each test case consists of three integers m, n, t (0 < m,n,t < 10000). Input is terminated by EOF.

Output

For each test case, print in a single line the maximum number of burgers Homer can eat without having beer. If homer must have beer, then also print the time he gets for drinking, separated by a single space. It is preferable that Homer drinks as little beer as possible.

Sample Input

3 5 543 5 55

Sample Output

1817

Problem setter: Sadrul Habib Chowdhury
Solution author: Monirul Hasan (Tomal)

Time goes, you say? Ah no!
Alas, Time stays, we go.
-- Austin Dobson

#include 
   
    #include 
    
     using namespace std;int dp[10001];int w[3];int sum[10001];int main(){
     
int m,n,t,i,j;
while(cin>>m>>n>>t)
{
w[1]=m;w[2]=n;
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
for(i=1;i<=2;i++)
{
for(j=0;j<=t;j++)
{
if(j>=w[i])
{
if(dp[j]
{
dp[j]=dp[j-w[i]]+w[i];
sum[j]=sum[j-w[i]]+1;
}
else if(dp[j]==dp[j-w[i]]+w[i])
sum[j]=max(sum[j],sum[j-w[i]]+1);
}
}
}
if(dp[t]==t)
cout< <
else
cout< <<" "< <
}
return 0;}


转载地址:https://blog.csdn.net/u010368749/article/details/19828543 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:最长公共上升子序列(LIS)
下一篇:uva147Dollars(完全背包)

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.249.68.18]2022年05月22日 23时23分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

php与json,PHP与json 2019-06-17 01:25:25
php xhtml格式,XHTML怎么打开?XHTML的规范的内容是什么? 2019-06-17 01:25:25
php lumen和laravel,Lumen - 基于 Laravel 构建的最快的 PHP 微框架(Micro-Framework)。 | Laravel 中文网... 2019-06-17 01:25:24
spring django php,Biny——腾讯开源的超轻量级 PHP 框架 2019-06-17 01:25:24
php环境安装包redhot,搭建php环境 2019-06-17 01:25:23
php继承 重写方法吗,PHP类和对象类的继承及重写(方法重写) 2019-06-17 01:25:22
php 图片处理慢,php常用图片处理类 2019-06-17 01:25:22
php 将中文字符转英文字母_php 提取字符串的中文首字母,如何考虑到英文和数字的情况... 2019-06-17 01:25:21
java 拼音首字母 高效_如何实现一个高效的拼音匹配库?解决多音字,首字母匹配等问题... 2019-06-17 01:25:21
java外部类调用匿名内部类_Java匿名内部类访问外部变量,为何需被标志为final?... 2019-06-17 01:25:20
java访问hfs服务_HFS的JAVA API_MapReduce服务 MRS_开发指南(适用于2.x及之前)_HBase应用开发_更多信息_华为云... 2019-06-17 01:25:20
java9 stream_Java9 Stream API改进 2019-06-17 01:25:19
C语言与JAVA内存管理_认识C和内存管理 2019-06-17 01:25:19
JAVA直接使用talib库_量化笔记:金融指数处理库talib介绍与安装 2019-06-17 01:25:18
java线程一定是thread_Java-Thread 线程 2019-06-17 01:25:17
1 n的和在main函数调用java_启动一个没有 main 函数的 java 程序 2019-06-17 01:25:17
cpp lexer java_ANTLR: 文法分析利器 (Ⅱ) 2019-06-17 01:25:16
java结果出来0.0_本人Java新手,请教各位大神,为啥输出结果是5个0哇? 2019-06-17 01:25:16
java流程拖拽功能_java拖曳功能代码示例 2019-06-17 01:25:15
JOptionPane在JAVA哪章_java预编译 预编译在java里属于哪一章的内容 2019-06-17 01:25:14