使用贪心法确定找零所需的最少硬币数量

Question

作为我的算法设计和分析课程的作业，我被要求使用贪婪的方法来确定找零所需的最少硬币数量。我想到了这种直观的方法：

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

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  scanf("%d",&sum);
  while(sum!=0) {
    if (sum<10&&sum>=1){
      ones=sum/1;
      sum-=ones;
    }
    else if(sum>=10&&sum<100){
      tens=sum/10;
      sum-=tens*10;
    }
    else if(sum>=100&&sum<=999){
      hundreds=sum/100;
      sum-=hundreds*100;
    }
    else{
      printf("Error");
      exit(0);
    }
  }

  printf("%d 0, %d , %d ",hundreds,tens,ones);
  return 0;
}

这种方法是贪心的吗？如何证明程序是正确的并且使用了贪心法？

Answer 1

你的代码不够贪心，因为它可能是最糟糕的：

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

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  if ((scanf("%d",&sum) == 1) && (sum >= 1) && (sum <= 999)) {
    while(sum!=0) {
      if (sum<10&&sum>=1){
        ones += 1;
        sum -= 1;
      }
      else if(sum>=10&&sum<100){
        tens += 1;
        sum -= 10;
      }
      else if(sum>=100&&sum<=999){
        hundreds += 1;
        sum -= 100;
      }
      else{ /* impossible case in fact */
        printf("Error");
        exit(0);
      }
    }

    printf("%d 0, %d , %d \n",hundreds,tens,ones);
  }
  return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra g.c
pi@raspberrypi:/tmp $ ./a.out
Enter a sum of money in range 1 to 999
997
9 0, 9 , 7

How do I prove that the program is correct

证明代码正确的（贪婪）方法是使用暴力检查从 1 到 999 的所有结果：

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

int main(){
  int n;

  for (n = 1; n <= 999; ++n) {
    /* the algo */
    int hundreds=0,tens=0,ones=0, sum = n;

    while(sum!=0) {
      if (sum<10&&sum>=1){
        ones += 1;
        sum -= 1;
      }
      else if(sum>=10&&sum<100){
        tens += 1;
        sum -= 10;
      }
      else if(sum>=100&&sum<=999){
        hundreds += 1;
        sum -= 100;
      }
      else{ /* impossible case in fact */
        printf("Error");
        exit(0);
      }
    }

    /* check */
    if ((hundreds*100 + tens*10 + ones) != n) {
      printf("error for %d : %d 0, %d , %d \n",n, hundreds,tens,ones);
      exit(0);
    }
  }
  puts("all ok");
  return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra g.c
pi@raspberrypi:/tmp $ ./a.out
all ok

Answer 2

这确实是一种贪婪的方法，但是你需要颠倒if-then-else的顺序。一般来说，greedy就是在当前时刻消耗你能消耗的最大数量。

您需要先检查最大的硬币。不需要 while 循环。

if(sum>=100) {
  hundreds=sum/100;
  sum-=hundreds*100;
}
if(sum>=10){
  tens=sum/10;
  sum-=tens*10;
} 
ones = sum;

Answer 3

建议代码如下：

干净地编译
不包含头文件那些内容没有用到
遵循公理：每行只有一个语句，每个语句（最多）一个变量声明。
执行所需的功能
执行适当的错误检查
执行 'greedy' 算法，尽可能快地消耗尽可能多的 'money'，使用最少的 'bills'

现在，建议的代码：

#include <stdio.h>


int main( void )
{
    int sum;

    do
    {
        printf("Enter a sum of money in range 1 to 999\n");
        if( scanf("%d",&sum) != 1)
        {
            fprintf( stderr, "scanf failed\n");
            return -1;
        }       
    } while( sum<0 || sum>999 );

    int hundreds = sum/100;
    sum          = sum % 100;
    int tens     = sum/10;
    sum          = sum % 10;
    int ones     = sum;

    printf("%d 0, %d , %d \n",hundreds,tens,ones);
}

提议的代码忽略了（美国）50 美元、20 美元、5 美元和 2 美元的钞票

使用贪心法确定找零所需的最少硬币数量

Determine the minimum number of coins required for giving a change using greedy approach

c

greedy