有个算法问题请教

ajinn

换硬币， 比如0.8元换成用25分，10分，2分和1分的硬币组合最少要几个硬币，
偶的算法是计算每一种等于0.8元的组合的硬币个数，
这样比较出最少的，不过换的钱大的时候，可能的组合很多，
偶的算法好像就比较笨，大家有什么好一些的办法吗？

lanche

虽然一看题目就知道最少需要5个硬币（即两个25分加三个10分，稍差的组合为三个25分+两个2分+一个1分，其它的就更差了），但要实现算法则要仔细考虑一下才行，用递归可能省力些。

dxz

动态规划

dxz

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
        fstream fin("coin.in");
        int  final, i, j, tmp;
        vector<int> coin;

        fin>>final;
        coin.resize(final+1, 1E;
        while(fin>>tmp)
                coin[tmp] = 1;

        for(i = 1 ; i <= final; ++i)
                for(j = 1; j < i; ++j)
                        if(coin + coin[j] < coin[i + j])
                                coin[i+j] = coin + coin[j];

        cout<<coin[final]<<endl;
        return 0;
}

dxz

coin.in
-----------------------------------------------
80
25 10 2 1

dxz

复杂度是n^2的，好像有更好的算法，一时没想到，容在想想

dxz

对不起，有错，改成：
for(i = 1 ; i <= final; ++i)
    for(j = 1; j < i; ++j)
         if(coin[i-j] + coin[j] < coin)
        coin = coin[i-j] + coin[j];

dxz

贪心的：       
                priority_queue<int> coin;
        while(fin>>tmp) coin.push(tmp);
        int count(0),res(final);
        while(res && !coin.empty()) {
                count += res/coin.top();
                res = res%coin.top();
                coin.pop();
        }
        if(res == 0 ) cout<<count<<endl;
        else                  cout<<"no"<<endl;

ajinn

动态规划不是很懂，

dxz, 能解释一下吗

dxz

动态规划方程：
coin = min(coin[i-j]+coin[j]) ; 1<=j<i

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
fstream fin("coin.in");
int final, i, j, tmp;
vector<int> coin;        //下标代表钱，纪录得是最少的组合所需的硬币数
                                 
fin>>final;                   //最终要形成的钱
coin.resize(final+1, 1E;  
while(fin>>tmp)
coin[tmp] = 1;  //形成每个硬币本面值只需一个这样的硬币

//每个i面值的硬币可以由(1，i-1),(2,i-2)......这些面值组成，记录这些组成中所需最少的
//值
for(i = 1 ; i <= final; ++i)
for(j = 1; j < i; ++j)
if(coin[i-j] + coin[j] < coin)
  coin = coin[i-j] + coin[j];
cout<<coin[final]<<endl;
return 0;
}

可以找算法书看看

lanche

有意思，可惜没在书店里找得着呀。

dxz

如果做过acm的题自己应该能推出来
不过据我所知，好像有更好的算法

lanche

acm又是什么?
我不是科班出身，可能很多理论跟算法都没接触过。

dxz

是大学生程序竞赛 ，你可以去acm.zju.edu.cn看看，相信会收获不少的 :   ，不过到时头大了可别怪我呦

quarkonics

dxz给推荐本参考书吧，对ACM很感兴趣