| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2068 人关注过本帖
标题:[讨论]出个题吧,DP...
只看楼主 加入收藏
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
收藏
 问题点数:0 回复次数:21 
[讨论]出个题吧,DP...
典型的DP题
http://acm.hdu.edu.cn/showproblem.php?pid=2069


Problem Description
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 cents.

Input
The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output
For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

Sample Input
11
26

Sample Output
4
13

搜索更多相关主题的帖子: class blank example amount target 
2007-09-04 13:13
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
收藏
得分:0 

让我很迷惑的是这句话
Your program should be able to handle up to 100 cents.

我觉得是"你的程序应该能够处理100美分内的情形"的意思

不过WA了N此后,发现似乎这句话的意思应该"你的程序应该处理硬币总数在100内的情形"

不过本人英语很烂,所以不排除是我的代码歪打正着的因素...


My BlogClick Me
2007-09-04 13:20
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 

刚好我DP烂
我来试试


2007-09-04 13:21
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
收藏
得分:0 
呵呵,做出来就把AC的截图贴出来吧

My BlogClick Me
2007-09-04 13:28
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
DP?貌似不需要。。。我想想。。。



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言,点击此处查看原因[/url]
C/C++算法习题(OnlineJudge):[url]http://yzfy.org/[/url]
2007-09-04 14:23
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
以下是引用雨中飞燕在2007-9-4 14:23:39的发言:
DP?貌似不需要。。。我想想。。。

不许老早就把答案说出来了.
我还要做呢
有点思路


2007-09-04 14:33
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用Eastsun在2007-9-4 13:20:06的发言:

让我很迷惑的是这句话
Your program should be able to handle up to 100 cents.

我觉得是"你的程序应该能够处理100美分内的情形"的意思

不过WA了N此后,发现似乎这句话的意思应该"你的程序应该处理硬币总数在100内的情形"

不过本人英语很烂,所以不排除是我的代码歪打正着的因素...

硬币种数不能超过100,但题目没说清楚,被激怒了,直接暴力解决了..........


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2007-09-04 15:32
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
以下是引用cwande在2007-9-4 15:32:26的发言:

硬币种数不能超过100,但题目没说清楚,被激怒了,直接暴力解决了..........

硬币种数才那么几种,何来100?
是硬币数目吧~~~~~~~~~~~~~~~




by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言,点击此处查看原因[/url]
C/C++算法习题(OnlineJudge):[url]http://yzfy.org/[/url]

2007-09-04 16:11
wentaiyou
Rank: 2
等 级:论坛游民
帖 子:68
专家分:17
注 册:2004-12-3
收藏
得分:0 

不是太明白什么意思.
就把他理解成是去商店用100元买100元以内的东西(假设不会出现几毛钱时).售货员可以用多少种找我钱的方法

#include "stdio.h"
void main()
{
int a,b,y1,y2,y3,y4,y5,y6,k=0;
printf("请输入物品价格(0-100):");
scanf("%d",&b);
a=100-b;
if (a>=50)
for(y1=0;y1<=(a/50);y1++)
for(y2=0;y2<=(a/20);y2++)
for(y3=0;y3<=(a/10);y3++)
for(y4=0;y4<=(a/5);y4++)
for(y5=0;y5<=(a/2);y5++)
for(y6=0;y6<=a;y6++)
if(y1*50+y2*20+y3*10+y4*5+y5*2+y6==a)
{
k++;
printf("%d-->50 %d-->20 %d-->10 %d-->5 %d-->2 %d-->1\n",y1,y2,y3,y4,y5,y6);
}

if (50>a && a >=20)
for(y2=0;y2<=(a/20);y2++)
for(y3=0;y3<=(a/10);y3++)
for(y4=0;y4<=(a/5);y4++)
for(y5=0;y5<=(a/2);y5++)
for(y6=0;y6<=a;y6++)
if(y2*20+y3*10+y4*5+y5*2+y6==a)
{
k++;
printf("%d-->20 %d-->10 %d-->5 %d-->2 %d-->1\n",y2,y3,y4,y5,y6);
}

if (20>a && a >=10)
for(y3=0;y3<=(a/10);y3++)
for(y4=0;y4<=(a/5);y4++)
for(y5=0;y5<=(a/2);y5++)
for(y6=0;y6<=a;y6++)
if(y3*10+y4*5+y5*2+y6==a)
{
k++;
printf("%d-->10 %d-->5 %d-->2 %d-->1\n",y3,y4,y5,y6);
}

if (10>a && a >=5)
for(y4=0;y4<=(a/5);y4++)
for(y5=0;y5<=(a/2);y5++)
for(y6=0;y6<=a;y6++)
if(y4*5+y5*2+y6==a)
{
k++;
printf("%d-->5 %d-->2 %d-->1\n",y4,y5,y6);
}

if (5>a && a >=2)
for(y5=0;y5<=(a/2);y5++)
for(y6=0;y6<=a;y6++)
if(y5*2+y6==a)
{
k++;
printf("%d-->2 %d-->1\n",y5,y6);
}

if (2>a && a >=1)
for(y6=0;y6<=a;y6++)
if(y6==a)
{
k++;
printf("%d-->1\n",y6);
}

if (a==0)
printf("不用找钱\n");
else
printf("一共有%d种找法\n",k);

}



感觉太长.请帮优化一下.小弟刚学.不是太懂算法.


假如回到过去.我能做些什么? 还是和现在这样有时间没事情?
2007-09-04 16:37
zzxwill
Rank: 1
等 级:新手上路
帖 子:398
专家分:0
注 册:2007-8-15
收藏
得分:0 
DP是?不好意思......

一分耕耘,一分收获。
2007-09-04 16:40
快速回复:[讨论]出个题吧,DP...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017260 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved