最优?步步贪婪，误入歧途！

wei_Y

看到一个算法问题，说的是:


有一个m*n的矩阵格子，里面每个格子有一个正数，一个人从左上要走到右下，每次只能往右或者下走，每经过一个格子他就拿走其分数，拿了格子里面的分数就没有了（为0），求如何走让分数最大。以下是难度：这个人这么走了2次，求怎么走让2次的总和最大。


思路:
先来走一次的，这个比较好写。
三种方法因为只能走右或下，所以选择两个中最大的来走。
第一种也就是贪婪的写法。

1. def tl(seq):
   
2.         count1,count2 = [],[]
   
3.         results = []
   
4.         def move(seq,a = [0,0],result = 0,remove = []):
   
5.                 if a == [len(seq)-1,len(seq[0])-1]:
   
6.                         count1.append(result)
   
7.                         count2.append(remove)
   
8.                 else:
   
9.                         if a[0] == len(seq)-1:
   
10.                                 move(seq,a = [a[0],a[1]+1],result = result+seq[a[0]][a[1]] ,remove = remove + [a])
    
11.                         elif a[1] == len(seq[0])-1:
    
12.                                 move(seq,a = [a[0]+1,a[1]],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
13.                         else:
    
14.                                 if seq[a[0]][a[1]+1] < seq[a[0]+1][a[1]]:
    
15.                                         move(seq,a = [a[0]+1,a[1]],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
16.                                 else:
    
17.                                         move(seq,a = [a[0],a[1]+1],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
18.         move(seq)

复制代码

这样做确保的是每一步都是最优，但有时候不会整体最优。

1. [
   
2. [0,3,4,5,6],
   
3. [1,2,3,4,5],
   
4. [5,6,7,8,1],
   
5. [3,5,6,7,0]
   
6. ]

复制代码

根据贪婪，走法是0-3-4-5-6-5-1-0，这样虽然确保了每一步的最优，但是无法保证了整体的最优，所以贪婪往往得到的是次优或次次，次次次- -。

这也就是只贪图眼前，而不够长远的做法，所以想解决问题还是不要贪婪！


第二种方法，暴力随机数。
想拼人品就把次数弄少点，想全点就把次数弄多点。

此方法太过暴力，慎用！
想试试的看一下这个问题。当时我用的随机数，那效率，没的说~，低到爆- -。

http://bbs.fishc.com/forum.php?m ... d=54578&ctid=12

第三种方法，动态规划。
动态规划是比较好的解决最优问题的方法，
也就是每走一步将结果暂存再将结果的可能性都列出，之后求最大。(不知道理解的对不对。)

将贪婪的修改一下就可以用啦。

1. def dp(seq):
   
2.         count1,count2 = [],[]
   
3.         results = []
   
4.         def move(seq,a = [0,0],result = 0,remove = []):
   
5.                 if a == [len(seq)-1,len(seq[0])-1]:
   
6.                         count1.append(result)
   
7.                         count2.append(remove)
   
8.                 else:
   
9.                         if a[0] == len(seq)-1:
   
10.                                 move(seq,a = [a[0],a[1]+1],result = result+seq[a[0]][a[1]] ,remove = remove + [a])
    
11.                         elif a[1] == len(seq[0])-1:
    
12.                                 move(seq,a = [a[0]+1,a[1]],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
13.                         else:
    
14.                                 move(seq,a = [a[0],a[1]+1],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
15.                                 move(seq,a = [a[0]+1,a[1]],result = result+seq[a[0]][a[1]],remove = remove + [a])
    
16.         move(seq)

复制代码

利用递归，最后返回最大值就好了。

当然也可以用迭代来完成，用迭代可能要嵌套多个循环，能理出头绪就试试吧~。

---------------------------------------凶残的化身----------------------暴力分割线--------------------------------------

回到问题，上面只是解决了一步，

P.S(我是问题:  有一个m*n的矩阵格子，里面每个格子有一个正数，一个人从左上要走到右下，每次只能往右或者下走，每经过一个格子他就拿走其分数，拿了格子里面的分数就没有了（为0），求如何走让分数最大。以下是难度：这个人这么走了2次，求怎么走让2次的总和最大。)

让第一次的最优了，那剩下的直接替换掉路径，再来一次最优那不就完成了！OK，说干就干。

加上

1. 
   
2.         a = max(count1)
   
3.         b = count2[count1.index(a)]
   
4.         for i in range(len(b)):
   
5.                 seq[b[i][0]][b[i][1]] = 0
   
6.         results.append(a)
   
7.         count1,count2 = [],[]
   
8.         move(seq)
   
9.         results.append(max(count1))

复制代码

栗子:

1. [
   
2. [0,3,0,2],
   
3. [0,3,0,0],
   
4. [0,3,0,0],
   
5. [0,0,0,4],
   
6. [0,0,0,4],
   
7. [0,3,0,0]]

复制代码

结果:
[17, 3]

也就是20，方法是动态规划本身是求的最优，应该是最优解了吧~。那他是怎么得来的呢?
第一次 ，那第二次要么取3，要么取2，所以取了3。这样应该就最大了吧。

但是还有一种可以全取到的走法。(不唯一。)



这样的结果是 22。显然最优。

现在问题来了:


我要说的显然不是如何编写最优解让挖掘鸡获取最大的效率T~T。(中国山东找蓝翔！)

动态规划还不能最优?
[url=]代码[/url]
其实是犯了一个错误，动态规划是整体上解决，但是我们是分步来看，局部动态规划，整体上就成了贪婪。谨慎！

不过，我没写出来直接求解的答案，只会后面进行处理。

1.         for i in range(len(count1)):                    
   
2.                 for c in range(len(count1[i:])):
   
3.                         temp = count1[i]+count1[c]
   
4.                         #将每一步的结果两两相加。
   
5.                         for j in range(len(count2[0])):
   
6.                                 if count2[i][j] == count2[c][j]:
   
7.                                         temp -= seq[count2[i][j][0]][count2[i][j][1]]
   
8.                         #重复的地方减少一个
   
9.                         results.append(temp)

复制代码

这样问题就解决了，整体上最优解，效率也变得有些慢。。

少鱼币的童鞋，
练思路的童鞋，
来捧场的童鞋，
只有鱼币奖励- -。





是时候展示你犀利的思路，风骚的代码了！。
(more and more fish money!)


砖

游客，如果您要查看本帖隐藏内容请回复

玉:

游客，如果您要查看本帖隐藏内容请回复

拈花小仙

不明觉厉，顶一个！

向往

很久没来鱼C了，看到了小甲鱼的微博，进来瞧一瞧，顶一顶！

opqrew99

刚刚开始学还不太明白学习学习!

bevin

卧槽 不当版主，隐藏的东西都看不了了

wei_Y

bevin 发表于 2014-12-8 20:08
卧槽 不当版主，隐藏的东西都看不了了

叫你不当，吃亏了吧。
话说我隐藏的东西一般没啥作用，就是听说隐藏回复的人多哈哈。

bevin

wei_Y 发表于 2014-12-8 20:12
叫你不当，吃亏了吧。
话说我隐藏的东西一般没啥作用，就是听说隐藏回复的人多哈哈。

算法太久没碰基本忘得差不多了，寒假有空准备补补，到时可以交流交流 哈哈哈

bevin

wei_Y 发表于 2014-12-8 20:12
叫你不当，吃亏了吧。
话说我隐藏的东西一般没啥作用，就是听说隐藏回复的人多哈哈。

感觉主要还是深度和广度搜索用的比较多，没事多做做欧拉计划上的题，会有提高的~

wei_Y

bevin 发表于 2014-12-8 20:35
感觉主要还是深度和广度搜索用的比较多，没事多做做欧拉计划上的题，会有提高的~

我还没学到嘛，欧拉计划我感觉要不能直接写出来要不就看半天没思路,没思路的还是大部分！
我没事就看兜兜给我说的那个外国站- -，全是算法的，还是英文。。

bevin

wei_Y 发表于 2014-12-8 20:42
我还没学到嘛，欧拉计划我感觉要不能直接写出来要不就看半天没思路,没思路的还是大部分！
我没事就看兜 ...

哈哈哈 哪个网站？  我最近太忙了，这几周要汇报三四篇论文

wei_Y

bevin 发表于 2014-12-8 20:44
哈哈哈 哪个网站？  我最近太忙了，这几周要汇报三四篇论文

http://www.checkio.org

我这里晚上打不开- -。

论文辛苦啊，等你不忙了得教教我，我这一个问题要搞好久好久。。

bevin

wei_Y 发表于 2014-12-8 20:51
http://www.checkio.org

我这里晚上打不开- -。

嗯，我也在群里的，到时在qq上说

微逻辑

看看砖和玉

wei_Y

bevin 发表于 2014-12-8 21:00
嗯，我也在群里的，到时在qq上说

嗯。

雨声绝晴

阔以哦{:1_1:}

qyt69985692

有点吃力。。。

戴宇轩

正在努力构思……

kenniya

非常支持！！！！！！！

1048870116

好厉害

因复仇而活

喵 我也恢复一个看看