动态规划之三--找零钱问题

题目：

   给定各种人民币面值的面值，根据所找零钱的总面值，在找给人民币数量做少的情况下各种人民币的面值级数量。

 

人民币面值为：25，15，10，5，2，1

所找零钱为： 57

 

 

/*
  Name: 找零钱问题
  Date: 01-12-07 01:40
  Description: 用的方法为动态规划方法
  测试1:
  ***************change.txt**************
  4 99
  5 20 80 90
  ******************************************
 结果:
  *************change_re.txt*************
  实找金额为:95
  5 1
  90 1
  *****************************************
  测试2:
  ***************change.txt**************
  5 99
  1 5 20 80 90
  ******************************************
  结果:
  *************change_re.txt*************
  实找金额为:99
  1 4
  5 1
  90 1
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX_change 200 //要找的零钱的总数

#define MAX_kind 30 //钱币面值的种类

#define MAX 9999

const char* INPUT_FILE = "change.txt";
const char* OUTPUT_FILE = "change_re.txt";

int u[MAX_kind][MAX_change];
int    coin[MAX_kind]; //钱币面值

int    b[MAX_kind][MAX_change]; //1:选择了coin[i-1] 2~∞:选择coin[i-1]的个数


int     real = 0; //实际找的零钱


FILE *in,*out;

void search_change(int n,int sum);
void print_change(int n,int sum);


void search_change(int n,int sum)
{
    int i,j,k,small,num = 1,s;
    
    for(j = 0; j <= sum ; j ++)
        u[0][j] = MAX;

    for(i = 1; i <= n; i ++)
        for(j = 1;j <= sum ;j ++)
        {
                        u[i][j] = u[i-1][j];
            small = u[i-1][j];
            for(k = 1 , s = coin[i-1] ; s <= j ; k ++ ,s += coin[i-1])
            {
                if(u[i][j-s] + k <= small) //注意这里的=号,否则结果就会出错!!!

                {
                    small = u[i][j-s] + k; //注意:这里是u[i][j-s] ,不是 u[i-1][j]

                    num = k + 1;
                }
            }
            u[i][j] = small;
            b[i][j] = num;
            num = 1;
        }

    real = sum;

    for(i = sum; i >= 0 ; i --)
    {
        for(j = n; j > 0 ; j -- )
        {
            if(b[j][i] > 1)
                return;
        }
        real--;
    }

/*调试用
    for(i = 0;i <=n;i++)
    {
        for(j = 0;j <=sum;j ++)
            printf("%d ",u[i][j]);
         printf("\n");
      }
    printf("*********************\n");
      for(i = 0;i <=n;i++)
    {
         for(j = 0;j <=sum;j ++)
              printf("%d ",b[i][j]);
         printf("\n");
       }
*/
}

//打印结果

void print_change(int n,int sum)
{
    if(n == 0 || sum < 0)
        return;
    if(b[n][sum] > 1)
    {
        print_change(n-1,sum - (b[n][sum]-1) * coin[n-1]);
//        printf("%d %d\n",n,sum-s[n-1]);

//        fputs(coin[n-1],out);

        fprintf(out,"%d %d\n",coin[n-1],b[n][sum] - 1);
    }
    else
    {
        print_change(n-1,sum);
//        printf("%d %d\n",n,sum);

    }
        
}

int main()
{
    int i,j,num,sum;
    
    if((in = fopen(INPUT_FILE,"r")) == NULL || (out = fopen(OUTPUT_FILE,"w")) == NULL)
    {
           printf("Can't open the file.");
           getch();
     return 1;
    }
    fscanf(in,"%d %d ",&num,&sum); //num:物品数量 sum:总共能装下的体积


    for(i = 0;i < num ;i ++)
    {
    fscanf(in,"%d ",&coin[i]); //s[i]:第i个物品的体积,v[i]: 第i个物品的价值

    }
/*调试
    for(i =0;i     {
       printf("%d ",coin[i]);
    }
    printf("\n**********************\n");
*/
    search_change(num,sum);


    fprintf(out,"实找金额为:%d\n",real);    
    print_change(num,real);

    fclose(in);
    fclose(out);

// getch();

    return 0;
}