发工资统计币种问题

问题描述

用贪心策略解决币种统计问题：某单位给职工发工资（精确到元）。为保证避免临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值（100,50,20,10,5,2,1元共7种）的张数，并验证币种统计是否正确。 编写算法实现问题求解。

问题分析

要使得取款的张数最少，应当尽量多的选择币值比较大的币种，然后拿总金额减去已经发放的金额，再考虑次大的币种。

代码实现

#include <iostream> 

using namespace std;

 int main() {

 //（100,50,20,10,5,2,1元共7种）

 int money = 0; cout << "请输入待找余的金额\n"; 

 cin >> money; int array[7] = {0, 0, 0, 0, 0, 0, 0}; 

 if (money >= 100) {

 array[0] = money / 100; 

 money = money % 100;

 cout << "找余100元" << array[0] << "张\t

";  } 

 if (money >= 50) {

 array[1] = money / 50;

 money = money % 50; 

 cout << "找余50元" << array[1] << "张\t"; } 

 if (money >= 20) { 

 array[2] = money / 20;

 money = money % 20; 

 cout << "找余20元" << array[2] << "张\t"; } 

 if (money >= 10) { 

 array[3] = money / 10; 

 money = money % 10;

 cout << "找余10元" << array[3] << "张\t"; }

 if (money >= 5) { 

 array[4] = money / 5;

 money = money % 5;

 cout << "找余5元" << array[4] << "张\t"; }

 if (money >= 2) { 

 array[5] = money / 2;

 money = money % 2;

 cout << "找余2元" << array[5] << "张\t"; } 

 if (money >= 1) {

 array[6] = money / 1; 

 money = 0;

 cout << "找余1元" << array[6] << "张\t"; } 

 return 0;

 }