ACM第三周心得

ACM第三周心得

                                         贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

基本思路；
贪心算法他和递归算法很类似，都是把一个复杂问题分解成子问题但是他所涉及的问题一般是求最优解的问题，这是与递归算法的第一个区别。局部最优求得整体最优这是第二个区别。最关键是贪心策略。（以上思路来自课堂老师讲解）
废话不多说来个例题。
1背包问题。]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30
那么思路如下
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优?
⑵每次挑选所占重量最小的物品装入是否能得到最优解?
⑶每次选取单位重量价值最大的物品，即性价比最高的成为解本题的策略。
重点思路。可能我们会觉得嗯，很对，就这麽分。但是为什么要这样。这样一定对吗/
我的想法如下**
这是一个比较简单的题，但是在啊简单也有调理的思路‘
我们首先看题目，有容量，物品，重量，价值。还有要求的总价值，
如果不管题目要求，我们显然可以按重量从小到大(重大到小），价值也是如此进行放置。然而这四纵方法并不对。这里也就是我我们强调的性价比。就像上面说的，贪心算法最关键的是贪心策略。其实还有一种想法。我们假设，这个最小物体的重量也比背包容量大。这样明显就要用性价比。另外我们注意这里物品可分割，当不可分是，3方案就不对，因此可以这样；
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则:对于单位重量价值一样的，则优先选择重量小的!这样就解决了。（注意；这样也可能不对，这里不在说。）

感想，这周对贪心进一步学习，与STL入门，一周过去还没能真正学会，今天就在学一遍。生死看淡不服就干，干掉一个是一个。另外印象很深的一点注；integer是整数的意思，读题是注意数字类型，否则很可能定义是出错’