2 zuoside  lord zuoside__lord 于 2017.01.07 15:20 提问

acm 里硬币问题 具体题目见下,采用穷举法时间超限,请问怎么修改

主页 讨论版 问题 名次 状态 统计
问题 L: 还是硬币问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 183 解决: 30
状态
题目描述
给你无限多个1元的硬币和2元的硬币,还有5元的硬币。

现在要你从这3种硬币中取n个硬币,使得他们的价值和为m

输入
多组输入

每组n , m

n < 1e6 , m <1e6

输出
总的方案数目

样例输入
2 3
样例输出
1

#include
int main()
{
int n,m;
int x,y,z,i,k,j;
i=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(x=0; x<=n; x++)
{
for(y=0; y<=n-x; y++)
{
for(z=0; z<=n-x-y; z++)
{
if((x+y+z==n)&&(x+2*y+5*z==m))
{
i++;
}

            }
        }
    }
    printf("%d\n",i);
}
return 0;

}

5个回答

dead911
dead911   2017.01.08 10:48
已采纳

假设1元,2元,5元硬币分别为a,b,c个

求满足约束条件
a + b + c = n            (1)         
的情况下,
a + 2*b + 5*c = m    (2)
解的个数。

直接用(1) - (2), 得到公式(3)

 b + 4c = m-n        (3)
 a被消去了,因为
 0 <= a <= n
 所以约束条件变为,
 0 <= b + c <= n

最终就变成了求
b+4c = m - n
有多少组整数解的问题

int resolve(int n, int m) {
    int b = 0, c = 0;
    int temp = m - n;
    int sum = 0;

    if ((temp % 4) > n) return 0;

    for (int c = (temp/4); c >= 0; --c) {
        b = temp - (c * 4);
        if (b + c <= n)
            sum += 1;
        else
            break;
    }

    return sum;

}

思路大概这样,代码随手写得...

dead911
dead911 回复Zindow: b + 4c = temp, temp对4取模就是b的最小值, b的最小值若已经大于n了,就不慢约束条件了.当时写代码的时候是这么觉得来着,现在细想其实也不需要这个判断, b+c <=n应该就够了
一年多之前 回复
Zindow
Zindow 请问为什么temp%4>n可以直接return 啊?
一年多之前 回复
zuoside__lord
zuoside__lord 回复尼奥普兰: 额,不知道,我用的是别人代码但是你们思路其实差不多,这个我没看,反正提交没有超时,,,,10^6算大数据么,应该不算吧。你博客不错有个东西好像符合我另一道题的理解需要虽然我没看出和这个有什么关系
一年多之前 回复
u011889952
u011889952 回复-lord: 这个思路确定不会超时???总觉得还是在大数据的时候还是会TLE吧
一年多之前 回复
zuoside__lord
zuoside__lord 原来你们都是这个思路啊,,,,,,,,
一年多之前 回复
u011889952
u011889952   2017.01.08 19:54

整数拆分问题,可以采用五边形数定理和母函数方法进行计算,详情参见我的博客:http://blog.csdn.net/u011889952/article/details/44813593

zuoside__lord
zuoside__lord 整数划分好,,,复杂,,,,,,,,但是你的博客多少还是提供了思路和代码,,,就是好多,,,
一年多之前 回复
lkysyzxz
lkysyzxz   2017.01.09 02:21

我第一时间想到了DP

lkysyzxz
lkysyzxz 回复尼奥普兰: 显然,数学解法会更快。
一年多之前 回复
u011889952
u011889952 DP是一种方法,但是这道题还有一种更快的方法。母函数或五边形数法
一年多之前 回复
crj8902
crj8902   2017.02.07 17:24

if (m < n)
return 0;
if (m == n)
return 1;
int temp = m - n;
int count = temp / 4;
count++;
return count;

zzhao114
zzhao114   2017.02.11 15:46

我来膜拜下大神的风采。。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
内存超限 和 超时问题(Maximum execution time)解决
问题一:内存超限利用循环分批导入; 每个循环内部开始处使用sleep(5);语句,做延迟执行,防止服务器内存同一时间占用过多,里面数字据情况修改; 每个循环内部结束地方使用 ob_flush();刷新输出缓冲 flush();将当前为止程序的所有输出发送到用户的浏览器 两者必须同时使用来刷新输出缓冲问题二:30秒运行超时的错误(Maximum execution time of 30 sec
素数C语言代码。ACM平台上总有些题目不是提交输出超限就是答案错误,,,,,,,,不懂,
素数代码对照, 原来代码百度,可以输出2,书上代码是不能输出2, #include #include int main() {     int n,i,k,j,flag;     scanf("%d",&j);     for(n=2; n     {         flag=1;         for(i=2; i         {             if(
ACM硬币问题
这是一道ACM之上的题目,在网上看到的大多是用贪心算法完成的,而贪心策略就是大面额的钱币尽可能的取,这样貌似没什么问题,比如15元,按照贪心策略来说尽可能的去面额的的及一张10+一张5。确实这些情况下,该贪心策略是没问题的,但是若是11呢,在这种情况下,按照贪心策略,就是取一张10,但是问题来了,没有1元的,就没有答案,而事实是取一张五元+三张2元的,这是最优的选择,所以对于该问题贪心策略是不可行
穷举法求解鸡兔同笼问题
#include #include using namespace std; int main() { //int heads = 23, feet = 60; int heads, feet; cout << "输入头,足的数量" << endl; cin >> heads >> feet; for(int i=0;i<35;i++) for (int j = 0;j<35; j
ACM:K: 抛硬币
ACM:K: 抛硬币 Description James得到了一堆有趣的硬币,于是决定用这些硬币跟朋友们玩个小游戏。在一个N行M列的表格上,每一个第i行第j列的格子上都放有一枚James的硬币,抛该硬币正面朝上的概率为Pij,所有抛硬币事件两两之间是相互独立的。 现在,玩家在M列硬币中,从每一列里各选择1枚,共M枚,构成一组。如此重复选择N组出来,且保证被选择过的硬币不能再选。选好组
ACM_程序设计竞赛:贪心算法:硬币问题
贪心算法:就是贪心的选取当前最优策略的算法设计方法。 有1元,5元,10元,50元,100元,500元的硬币
数据结构-16枚硬币问题
数据结构-16枚硬币问题本题主要考查对图的结构和图的广度优先遍历操作的掌握。 实现效果: 什么是图? 定义:图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。图又分为有向图、无向图,有向图即边为有向边的图,无向图即边没有方向的图。图的两种遍历(深度优先遍历、广度优先遍历)深度优先遍历:(Dept
HDU 3348 coins 贪心 最少/最多硬币问题
题意是说现在给你一定数目的1角,5角,1元,5元和10元硬币,要买一个P角的东西(注意单位是毛......一开始没仔细看直接当成元算的),问最少和最多分别用多少硬币能买到,如果凑不出正好的钱,则输出“-1 -1”。     最少多少硬币比较好处理一些,直接用贪心的算法,从面值最大的硬币开始向下一个个遍历就可以了,因为为了花费最少则一定要把能花的最大面值硬币花了。如果遍历后发现没办法凑齐,则输出“
兑换硬币(简单版,枚举)
这道题在ZQUOJ上的名字确实是枚举法,但是做的方法却是穷举法,刚开始我一直往枚举的方向思考,陷入一个死循环,如果有可以用枚举解决这道题的,麻烦在下面解答一二,感谢; ps:最后这道题也是让我同学给我看答案我才知道这道题用穷举法的 Description Alice喜欢收集东西(collect things)。她听说以前的硬币(coin)是用一种叫做镍的金属做的,而镍是稀有金属,自从国家回收旧
钱币组合问题(一):(每种硬币不限次数)
钱币组合问题(一):(每种硬币不限次数) 假设我们有8种不同面值的硬币{1,2,5,10,20,50,100,200},用这些硬币组合够成一个给定的数值n。例如n=200,那么一种可能的组合方式为 200 = 3 * 1 + 1*2 + 1*5 + 2*20 + 1 * 50 + 1 * 100. 问总过有多少种可能的组合方式? 思路一:暴力穷举 每种硬币最多为N/coin