今天在论坛上看见有个人在讨论书包算法，于是好奇就也做了个（反正以后也要学的，嘿嘿！）已经知道有面值为： 100，50，30，10的钱，如输入：150，就输出100和50。输入280就输出2个100元，一个50元，3个10元，以此类推。。。可写出来的总是错错错！！代码如下：
#include<stdio.h>
void ok(int mianzhi,int f)
{
    printf("%d个%d元 ",f,mianzhi);
}
int main(void)
{
    int a,b[4]={100,50,30,10},f;
    scanf("%d",&a);
    for(f=0;f<4;f--)
    {
        if(a<b[f])
        {    if(f==3)
                ok(a,1);
            else
                continue;
        }
        else if(a>b[f])
        {
            ok(b[f],a/b[f]);
            if(a%b[f]==0)
                break;
            else
            {
                a=a%b[f];
                continue;
            }
            
        }
        else if(a==b[f])
        {
            ok(b[f],1);
            break;
        }
        
    }
    getch();
    return 0;
}
逻辑混乱 代码有点乱，可以的话帮忙修改下~~.错误的地方是输入100结果正确，输入120.输出的结果要我喷血！！乱七八糟的！
都帮忙帮忙啦~~~不过我写这个程序也是为了帮别人。。哈哈！！

for(f=0;f<4;f--)
这块就不对啊，f初始化为0，你还敢--?
结果肯定是烂七八糟的东西呀

#include<stdio.h>
void ok(int mianzhi,int f)
{
    printf("%d个%d元 ",f,mianzhi);
}
int main(void)
{
    int a,b[4]={100,50,30,10};
    while(scanf("%d",&a)==1)
    {
        if(a>=b[0])
        {
            ok(b[0],a/b[0]);
            a-=(a/b[0])*b[0];
        }
        if(a>=b[1])
        {
            ok(b[1],a/b[1]);
            a-=a/b[1]*b[1];
        }
        if(a>=b[2])
        {
            ok(b[2],a/b[2]);
            a-=a/b[2]*b[2];
        }
        if(a>=b[3])
            ok(b[3],a/b[3]);
    }
    return 0;
}
不知道符不符合要求

........我太粗心了..改改

真的不可大意啊，就错了那么一点点，大家千万别和我一样啊....，现在搞定了，谢谢楼上的啦

这种算法，有本算法书就可以了，写好伪代码的，任何程序语言都可以找着写，没必要现在去啃它。关键的地方是对具体的某个问题，它到底适用哪个现成的算法？可能是多个算法的组合吗？或者它似是而非？或者根本没有现成的算法可以套用？判断正确，才是正道，不是背熟了一大堆算法就可以解决现实问题的。这个世界如果那么简单，就根本没有问题可言，做人很无趣的。

看来楼主的背包物品每件不止一个  所以这就退化成了最优砝码问题

楼主要得到的解是要用最少的人民币张数来构造一个面值 这就是最优砝码问题

状态转移方程为 a[i] = min{a[i-v[j]]+1,a[i]} 其中i为你要构造的人民币面值v[j]

为你现在手中拿的人民币面值 所以应该用二重循环来动态维护面值散列表

0-1背包问题应该是a[i][j] = max{a[i-1][j],a[i-1][j-w[i]]+v[i]};

w[i]是第i件物品的重量 v[i]是第i件物品的价值

[ 本帖最后由 laoyang103 于 2011-9-22 19:35 编辑 ]

这是教材上的 贪心例题...

[ 本帖最后由 BlueGuy 于 2011-9-22 21:38 编辑 ]

但是这个题可以用dp做

能不能写下是怎么做的??