c语言背包问题贪心算法,C/C++语言算法篇（一）：贪心算法

贪心算法

正所谓人人都有贪心，C语言算法上的贪心可不是实际意义上的贪心，C语言结构上的贪 心可以说满足两个条件：贪心选择性质和最优子结构性质。满足这两个条件的话就可以尝试用贪心算法解决问题。

贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。

应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题在程序的运行过程中无回溯过程。

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可用贪心算法求解的关键。例如原问题S={a1，

a2，…，ai，…， an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题

S-{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质，

算法步骤

1、 选择算法结构

就是说你必须要选择一个贪心的方案，就好比如你去买菜，什么菜最好，什么菜买了才不会吃亏(这又关于另一个问题，物品的价值，越高越好)。当然啦，你愿意当个大傻个让别人扎一刀，那也无所谓的。

2、 局部最优解

这里说的呢就是实战的过程最优解，就好比如你要买一袋苹果，一般来说肯定拿最大的先(这里就是一个局部最优解)，接着就是摊主上第二大的苹果，以此类推，最终的出的结果就是贪心的后果咯。

3、 算法实战

1、船装载问题

有一条船的装载量一定，要