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

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，数学归纳法证明每一步均可通过贪心选择得到最优解本回答被提问者采纳