Question

贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么？怎样说明一个问题具有贪心选择呢

Answer 1

一般都是要最省事的比如
设有n中不同面值的硬币，个硬币的面值春雨数组T[1：n]中，现在要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意签署0<=m<=20001，设计一个用最少硬币找钱m的方法。

用贪心算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。这样最少
程序实例
#include<stdio.h>

void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;

}

for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d张\n",T[i],coins[i]);
printf("\n");
}

Answer 2

贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来得到。
就是说，你需要证明当前问题可以通过选择最好的那个元素（比如01背包，总能够通过选择当前重量最小的物品来得到最优解）来解决问题
证明：（每一步所做的贪心选择最终导致问题的整体最优解）
//基本思路：考察一个问题的最优解，证明可修改该最优解，使得其从贪心选择开始，然后用数学归纳法证明每一步都可以通过贪心选择得到最优解
1，假定首选元素不是贪心选择所要的元素，证明将首元素替换成贪心选择所需元素，依然得到最优解；
2，数学归纳法证明每一步均可通过贪心选择得到最优解