概述
每一步都根据当前的信息做出选择，一担选择，都不会改变（不会反悔）
用局部的最优解，达到整体的最优解
海盗船
海盗船
实际问题：一群海盗截获了一艘装满各种金银珠宝和古董的货船，每一件宝物都价值连城一旦打碎就失去了价值。海盗船的载重量为C，每件宝物的重量为Wi，海盗们应该如何把尽可能多的宝物装上船？
分析，每次选最小的
int main()
{
int arr[10] = {
2,34,6,67,33,47,56,567,1,4 };
heapsort(arr, 10);
int max = 207;
int n = 0, sum = 0;
for (int i = 0; i < 10; i++)
{
if (sum > max)
{
break;
}
sum += arr[i];
n++;
}
printf("%d ", n);
return 0;
}
种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n
朵花？能则返回True，不能则返回False。注意:
1、数组内已种好的花不会违反种植规则。 2、输入的数组长度范围为 [1, 20000]。 3、n 是非负整数，且不会超过输入数组的大小。
```c
int main()
{
int arr[5] = {
1,0,0,0,1 };
int n = 1;
int i = 0;
int count = 0;
for (i = 0; i < 5; )
{
if (arr[i] == 1)//遇到花就跳两格
{
i += 2;
}
else if (arr[i - 1] == 1 && i > 0)//不是花，但是他前面有花且不是第一个，跳1格
{
i += 1;
}
else if (arr[i + 1] == 1 && i+1<5)//不是花，但他后面有花，且不是最后一个，跳3格
{
i += 3;
}
else//前后都没花
{
arr[i] = 1;
i += 2;//跳两格
count++;
if (count == n)
{
printf("yes");
}
}
}
return 0;
}
小行星碰撞
给定一个整数数组 asteroids，表示在同一行的小行星。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10
永远不会发生碰撞。示例 2：
输入：asteroids = [8,-8] 输出：[] 解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5] 输出：[10] 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下
10 。示例 4：
输入：asteroids = [-2,-1,1,2] 输出：[-2,-1,1,2] 解释：-2 和 -1 向左移动，而 1 和 2
向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。提示：
2 <= asteroids.length <= 104 -1000 <= asteroids[i] <= 1000 asteroids[i] != 0
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
//正数往右走，负数往左走
#include<math.h>
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize)
{
int n = 0;
while (1)
{
int prev = 0;
int next = 1;
//每次都重左到右扫描一遍
while (next < asteroidsSize)// 每次只消一个,这个循环是把所有的都消掉,能够保证两者除0外都挨着
{
if (asteroids[prev] * asteroids[next] < 0)
{
//1.背靠背不能碰撞
//如-9 8 32 9
//如-9 0 8 9//我们不能够让前后都往后走一步，因为0是有隐患的，我们不走0
//prev next
// prev next
//-9 0 8 9
if (asteroids[prev] < 0)//前面的往前走，后面的往后走就不符合
{
prev = next;
next++;
//背靠背不能再碰了，就进入下一个循环
continue;
}
//发生了碰撞,左边大
if (abs(asteroids[prev]) > abs(asteroids[next]))
{
asteroids[next]=0;
n++;
}
if (abs(asteroids[prev]) < abs(asteroids[next]))
{
asteroids[prev] = 0;
n++;
}
if (abs(asteroids[prev]) == abs(asteroids[next]))
{
asteroids[next] = 0;
asteroids[prev] = 0;
n+=2;
}
break;//贪心不贪婪
}
//如果前后相乘为0
//0 3,左边的等于0
if (asteroids[prev] == 0)
{
prev = next;
next++;
}
//如果前后相乘为0
//3 0,右边的等于0
if (asteroids[next] == 0)//左边不动
{
next++;
}
else
{
//prev next
//7 0 0 4 -2
//方向相同,就前进一步
prev = next;//要跨过0
next++;
}
}
//出来了，next就大于size了
if (next > asteroidsSize)
{
break;
}
}
*returnSize = asteroidsSize - n;//返回剩余的
int *ret = (int *)malloc(sizeof(int)*(asteroidsSize - n));
int i,j=0;
for (i = 0; i < asteroidsSize; i++)
{
if (asteroids[i])
{
ret[j++] = asteroids[i];
}
}
return ret;
}