C语言及程序设计进阶例程-27 贪心法问题求解

贺老师教学链接 C语言及程序设计进阶 本课讲解

找零钱问题及其求解

#include <stdio.h>
int main ( )
{
    int money[10]={100,50,10,0};  /*最大面额的硬值面值排在最前面，将被优先处理*/
    int x;   /*找零金额*/
    int i=0, n=0, m;
    scanf("%d", &x); /*输入找零金额*/
    while(x>0 && money[i]!=0)   /**/
    {
        m=x/money[i];   /*要找多少个面额为money[i]的硬币。i初值为0，体现从币值最大的硬币开始考虑*/
        n+=m;           /*n初值为0，记录零钱总枚数*/
        x-=m*money[i];  /*剩余的零钱金额*/
        i++;            /*将继续考虑下一种面额的硬币*/
    }
    if(x==0)
        printf("%d\n", n);
    else
        printf("\n");
    return 0;
}

最优装载问题及其求解

#include <stdio.h>
#define N 5  /*最多可能集装箱数*/
int main()
{
    int w[N]; /*存放集装箱重量，w[i]是第i个集装箱的重量*/
    int x[N]= {0}; /*用来存放集装箱的取舍，x[i]为1，表示i集装箱要装船，为0不装*/
    int t[N];   /*用来存放w[i]的下标*/
    int c;    /*货船总载重量*/
    int n;    /*集装箱个数*/
    int i, j, tmpw, tmpt;    /*用于控制循环及用于交换的临时变量*/
    printf("输入货船的最大载重量：");
    scanf("%d", &c);
    printf("输入集装箱个数：");
    scanf("%d", &n);
    printf("输入每个集装箱的质量：\n");
    for(i=0; i<n; i++)
        scanf("%d", &w[i]);
    /*在数组t[]中记录下原先集装箱的下标*/
    for(i=0; i<n; i++)
        t[i]=i;
    /*步骤1：按集装箱重量排序，同时在t数组中保存原有的顺序*/
    for(i=0; i<n-1; i++)
        for(j=0; j<n-i-1; j++)
            /*如果前大后小，要交换*/
            if(w[j]>w[j+1])
            {
                tmpw = w[j];  /*交换w[]中的元素*/
                w[j] = w[j+1];
                w[j+1] = tmpw;
                tmpt = t[j];  /*同时交换代表他们原先下标的数组*/
                t[j] = t[j+1];
                t[j+1] = tmpt;
            }
    /*步骤2：根据排好序的数组w[]，在不超重的情况下，确定哪些集装箱*/
    for(i=0; i<n && w[i]<=c; i++)
    {
        x[t[i]] = 1;     /*w[i]要装载，其原下标是t[i]，所以x[t[i]] = 1*/
        c = c - w[i];    /*调整c值*/
    }
    /*步骤3：输出结果*/
    for(i=0; i<n; i++)
    {
        if(x[i]==1)
            printf("BOX:%d ", i);
    }
    return 0;
}