数模学习第7天~
贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。
贪心算法的基本思路
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
- 不能保证求得的最后解是最佳的；
- 不能用来求最大或最小解问题；
- 只能求满足某些约束条件的可行解的范围。
求解过程：
- 从问题的某一初始解出发；
- while 能朝给定总目标前进一步 do 求出可行解的一个解元素；
- 由所有解元素组合成问题的一个可行解；
贪心算法——背包问题
给定n个物品和一个容量为C的背包，物品i的重量是w[i],其价值为v[i],背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大。（与动态规划中01背包的相区分，用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直到背包装满。）
int KnapSack (int W[],int V[],int N,int C)
{
double X[10]={0};
int maxValue=0;
for(int i=0;W[i]<C;i++)//循环直到背包装不下
{
X[i]=1;//将第i个物品放入背包
maxValue+=V[i];
C=C-W[i];
X[i]=(double)C/W[i];
maxValue+=X[i]*V[i];
return maxValue;
}
}
