QQ登录

只需一步,快速开始

搜索
查看: 409|回复: 22

[活动专区] 小练习:20171009 矩阵和

[复制链接]
最佳答案
466 
累计签到:685 天
连续签到:2 天
发表于 2017-10-9 10:41:39 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-10-16 20:51 编辑

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。

什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives

这里已经有了500余题。


                               
登录/注册后可看大图


要求:

以python语言完成,如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成,即10.2 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。题目不难,大家看看谁的效率高。

-- 回帖需写明解题思路,鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难,为此略过一部分偏难的题目 --


                               
登录/注册后可看大图
345


在一个矩阵中选择部分元素,使得每个元素都是所在的行和列中唯一被选中的元素,这些元素的和的最大值定义为矩阵的矩阵和。例如,如下矩阵的矩阵和为3315 ( = 863 + 383 + 343 + 959 + 767):

  7  53 183 439 863
497 383 563  79 973
287  63 343 169 583
627 343 773 959 943
767 473 103 699 303
求如下矩阵的矩阵和:

  7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
30 
累计签到:130 天
连续签到:31 天
发表于 2017-10-9 11:53:59 | 显示全部楼层
  1. oM = '''7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
  2. 627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
  3. 447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
  4. 217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
  5. 960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
  6. 870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
  7. 973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
  8. 322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
  9. 445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
  10. 414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
  11. 184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
  12. 821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
  13. 34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
  14. 815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
  15. 813 883 451 509 615  77 281 613 459 205 380 274 302  35 805'''

  16. s = oM.split('\n')

  17. t = []
  18. for i in range(len(s)):
  19.     t.append(s[i].split())

  20. length = len(t[0])
  21. temp = []
  22. choice = []
  23. for each in t:
  24.     maxn = 0
  25.     for k in range(length):
  26.         cell = int(each[k])
  27.         if maxn < cell and k not in temp:
  28.             maxn = cell
  29.             index = k
  30.     else:
  31.         temp.append(index)
  32.         choice.append(maxn)
  33.         
  34. print(sum(choice))
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
50 
累计签到:329 天
连续签到:7 天
发表于 2017-10-9 19:47:14 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-10-9 19:48 编辑

好吧,这题又是典型的线性规划题目,祭出线性规划库pymprog,秒出答案
再次安利一下这个强大的第三方库http://bbs.fishc.com/thread-96997-1-1.html
  1. from pymprog import *
  2. g = (
  3. (7,53,183,439,863,497,383,563,79,973,287,63,343,169,583),
  4. (627,343,773,959,943,767,473,103,699,303,957,703,583,639,913),
  5. (447,283,463,29,23,487,463,993,119,883,327,493,423,159,743),
  6. (217,623,3,399,853,407,103,983,89,463,290,516,212,462,350),
  7. (960,376,682,962,300,780,486,502,912,800,250,346,172,812,350),
  8. (870,456,192,162,593,473,915,45,989,873,823,965,425,329,803),
  9. (973,965,905,919,133,673,665,235,509,613,673,815,165,992,326),
  10. (322,148,972,962,286,255,941,541,265,323,925,281,601,95,973),
  11. (445,721,11,525,473,65,511,164,138,672,18,428,154,448,848),
  12. (414,456,310,312,798,104,566,520,302,248,694,976,430,392,198),
  13. (184,829,373,181,631,101,969,613,840,740,778,458,284,760,390),
  14. (821,461,843,513,17,901,711,993,293,157,274,94,192,156,574),
  15. (34,124,4,878,450,476,712,914,838,669,875,299,823,329,699),
  16. (815,559,813,459,522,788,168,586,966,232,308,833,251,631,107),
  17. (813,883,451,509,615,77,281,613,459,205,380,274,302,35,805))

  18. begin('Euler345')
  19. row = range(15)
  20. col = range(15)
  21. iprd = iprod(row,col)
  22. T = var('X', iprd, bool)
  23. [sum(T[i,j] for i in row)==1 for j in col] #行约束
  24. [sum(T[i,j] for j in col)==1 for i in row] #列约束
  25. maximize(sum(T[i,j]*g[i][j] for i in row for j in col)) #求最大值
  26. solve()
复制代码

GLPK Simplex Optimizer, v4.60
30 rows, 225 columns, 450 non-zeros
      0: obj =  -0.000000000e+00 inf =   3.000e+01 (30)
     15: obj =   6.708000000e+03 inf =   0.000e+00 (0)
*    82: obj =   1.393800000e+04 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.60
30 rows, 225 columns, 450 non-zeros
225 integer variables, all of which are binary
Integer optimization begins...
+    82: mip =     not found yet <=              +inf        (1; 0)
+    82: >>>>>   1.393800000e+04 <=   1.393800000e+04   0.0% (1; 0)
+    82: mip =   1.393800000e+04 <=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
[Finished in 0.2s]
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
5 
累计签到:225 天
连续签到:118 天
发表于 2017-10-9 23:05:20 | 显示全部楼层
本帖最后由 xindong 于 2017-10-10 10:30 编辑

这运算量有点太大了吧。写了一个递归函数,验证了低阶的结果没有问题。但是算到15阶,太久了。
昨晚笔记本休眠了,不知道需要多久,算10阶大概需要29秒,算11阶275秒,算12阶1个小时,算13阶 半天,这样下去算到15阶   难道是我的电脑的问题,还是算法上太臃肿了?
今天早上加上了代码注释
又加上了运行时间计算


大概写个结果吧
  5阶 3315  
  6阶 4578
  7阶 5712
  8阶 7114
  9阶 7818
10阶 8779
11阶 9876 运行时间275秒
12阶 11230 运行时间 3073


# -*- coding: utf-8 -*-
"""
Created on Mon Oct  9 15:44:11 2017

"""
#矩阵求和递归函数
def matrix_sum(max_level, current_level, sum_level, selectable):


# max_level 矩阵阶数
# current_level 当前遍历阶数
# sum_level 截止到当前阶,所选矩阵单元之和
# selectable 当前阶可选位置  一维列表   单元值为1不可选,单元值为0, 可以选择

#全局变量  val_2d  -- 二维矩阵数据
#全局变量  sum_max -- 矩阵和最大值数据

    global val_2d
    global sum_max
   
   
    if (current_level==max_level-1):
    #如果当前行是最后一行,则找到最后且只有的一个单元位置
        index=0
        while(selectable[index]==1):
            index = index +1
        #取出单元数值,并和之前的矩阵单元和相加,判断是否是最大值,如果是,存储最大值
        sum_val=sum_level+val_2d[current_level][index]
        if sum_val>sum_max:
            sum_max=sum_val
        return sum_max
    else:
    #如果当前行不是最后一行,则当前行可选的位置个数为 max_level-current_level
        selected=[j for j in selectable] #selected 存储本层可选的位置
        selected_level=[j for j in selectable]  # selected_level 加上本层已选单元后,可选位置
        index=0
        for i in range(0,max_level-current_level):
            #找到本层可选的位置   selected=0的位置是可以选的
            while (selected[index]==1):
                index=index+1
            #找到可选位置后,占坑,标为1,表示以后不可以选
            selected[index]=1
            #本层选定位置也做出标记
            selected_level[index]=1
            #选定本层单元后,将单元值存入矩阵元素和变量中
            sum_level_current=sum_level + val_2d[current_level][index]
            #调用递归函数
            sum_levelN=matrix_sum(max_level, current_level+1,sum_level_current, selected_level)
            #把之前本层标记占用的位置恢复出来,下次循环会占用不同的位置
            selected_level[index]=0           
    return sum_levelN   

#读取数据文件
#数据文件存取格式为
'''
7  53 183 439 863
497 383 563  79 973
287  63 343 169 583
627 343 773 959 943
767 473 103 699 303
'''

import datetime
starttime = datetime.datetime.now()


datafile_path="C:/E_Users/Python/fishc/data5.txt"
f = open(datafile_path)
X = f.readlines()
f.close()

#定义全局变量
global val_2d
global sum_max

#设定 sum_max初值
sum_max=-999999999999

#设定二维列表初值
val_2d=[1]


#将读取的字符串数据进行分割,转换为二维整型列表
index=0
for i in X:
     D  = i.split()
     val_D= [int(j) for j in D ]
     tmp=[0 for j in D]
     if(index==0):
         val_2d[0]=val_D
     else:
         val_2d.append(val_D)
     index=index+1
     
#取得二维整型列表行数和列数  (假定读取的是规则数据)     
column_val=len(val_2d)
row_val=len(val_2d[0])

#设定可选位置列表  select_m长度和矩阵一行元素个数相同
#对第一行矩阵数据而言,初始状态下,所有的位置均可以选择,故select_m所有单元为0
select_m=[0 for i in val_2d[0]]

#调用矩阵和递归函数,输入矩阵行数,当前行,当前矩阵数值和,可选位置
sum_N=matrix_sum(row_val, 0, 0, select_m)

endtime = datetime.datetime.now()

print(sum_N)
print ((endtime - starttime).seconds)




点评

我很赞同!: 5.0
记得先导入itertools的permutations库  发表于 2017-10-10 11:02
而且穷举的话,你也写得太复杂了,其实只要1行就够了^_^,而且运算时间是你的一半。 maxx = 0; for each in permutations(range(9)): maxx = max(maxx, sum(g[i][each[i]] for i in range(9))); print(maxx);  发表于 2017-10-10 11:00
我很赞同!: 5
穷举的话,是这个样子的,没上1阶几乎就是10倍的运算量,指数级递增。按照你笔记本的运算速度,算出15阶大概1个月左右。  发表于 2017-10-10 10:46
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
50 
累计签到:329 天
连续签到:7 天
发表于 2017-10-10 09:41:03 | 显示全部楼层
另一种不用动态规划库的方法就是穷举,但是穷举效率肯定很低,不过代码也很简单。
  1. from itertools import permutations as pt
  2. g = (
  3. (7,53,183,439,863,497,383,563,79,973,287,63,343,169,583),
  4. (627,343,773,959,943,767,473,103,699,303,957,703,583,639,913),
  5. (447,283,463,29,23,487,463,993,119,883,327,493,423,159,743),
  6. (217,623,3,399,853,407,103,983,89,463,290,516,212,462,350),
  7. (960,376,682,962,300,780,486,502,912,800,250,346,172,812,350),
  8. (870,456,192,162,593,473,915,45,989,873,823,965,425,329,803),
  9. (973,965,905,919,133,673,665,235,509,613,673,815,165,992,326),
  10. (322,148,972,962,286,255,941,541,265,323,925,281,601,95,973),
  11. (445,721,11,525,473,65,511,164,138,672,18,428,154,448,848),
  12. (414,456,310,312,798,104,566,520,302,248,694,976,430,392,198),
  13. (184,829,373,181,631,101,969,613,840,740,778,458,284,760,390),
  14. (821,461,843,513,17,901,711,993,293,157,274,94,192,156,574),
  15. (34,124,4,878,450,476,712,914,838,669,875,299,823,329,699),
  16. (815,559,813,459,522,788,168,586,966,232,308,833,251,631,107),
  17. (813,883,451,509,615,77,281,613,459,205,380,274,302,35,805))

  18. maxx = 0
  19. for each in pt(range(15)):
  20.         tmp = sum(g[i][each[i]] for i in range(15))
  21.         maxx = max(maxx, tmp)
  22. print(maxx)
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
197 
累计签到:231 天
连续签到:1 天
发表于 2017-10-10 10:34:43 | 显示全部楼层
jerryxjr1220 发表于 2017-10-10 09:41
另一种不用动态规划库的方法就是穷举,但是穷举效率肯定很低,不过代码也很简单。

15 * 15 的矩阵,假设行号不变,仅变动列号,就是15个元素的全排列;
也就是 :
15!   =  1307674368000

1.3万亿,要算好久~
一般,用蒙特卡罗算法来随机抽样,也能较快的搜索到答案

点评

我很赞同!: 5.0
我很赞同!: 5
是要算好久,所以我只列了程序而没有执行,算10x10的矩阵还行,15x15的就太大了。 但是蒙特卡洛算法我知道可以求出某个解,但是怎么确定这个解就是最大值,如果不是全部遍历的话?  发表于 2017-10-10 10:39
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
1 

尚未签到

发表于 2017-10-10 12:21:06 | 显示全部楼层
采用递归,用hash缓存求过的解
答案13938
  1. import time

  2. test1 = [[7,53,183,439,863],[497,383,563,79,973],[287,63,343,169,583],[627,343,773,959,943],[767,473,103,699,303]]
  3. matrix1=[[7,53,183,439,863,497,383,563,79,973,287,63,343,169,583],[627,343,773,959,943,767,473,103,699,303,957,703,583,639,913],[447,283,463,29,23,487,463,993,119,883,327,493,423,159,743],[217,623,3,399,853,407,103,983,89,463,290,516,212,462,350],[960,376,682,962,300,780,486,502,912,800,250,346,172,812,350],[870,456,192,162,593,473,915,45,989,873,823,965,425,329,803],[973,965,905,919,133,673,665,235,509,613,673,815,165,992,326],[322,148,972,962,286,255,941,541,265,323,925,281,601,95,973],[445,721,11,525,473,65,511,164,138,672,18,428,154,448,848],[414,456,310,312,798,104,566,520,302,248,694,976,430,392,198],[184,829,373,181,631,101,969,613,840,740,778,458,284,760,390],[821,461,843,513,17,901,711,993,293,157,274,94,192,156,574],[34,124,4,878,450,476,712,914,838,669,875,299,823,329,699],[815,559,813,459,522,788,168,586,966,232,308,833,251,631,107],[813,883,451,509,615,77,281,613,459,205,380,274,302,35,805]]
  4. maxdict = {}

  5. def sliceMatrix(matrix, size):
  6.         return [matrix[i][:size] for i in range(size)]

  7. def getmax(matrix, usedCol, row):
  8.         global maxdict
  9.         r = maxdict.get((str(usedCol),row), 0)
  10.         if r > 0:
  11.                 return r
  12.         cols = set(range(len(matrix))) - usedCol
  13.         maxn = -1
  14.         if row == len(matrix)-1:
  15.                 for c in cols:
  16.                         if matrix[row][c] > maxn:
  17.                                 maxn = matrix[row][c]
  18.         else:
  19.                 for c in cols:
  20.                         s = matrix[row][c] + getmax(matrix, usedCol | set([c]), row+1)
  21.                         if s > maxn:
  22.                                 maxn = s
  23.         maxdict[(str(usedCol), row)] = maxn
  24.         return maxn

  25. #print(getmax(test1, set([]), 0)) #3315                       
  26. st = time.time()
  27. maxdict = {}
  28. #print(getmax(sliceMatrix(matrix1, 10), set([]), 0)) #13938
  29. print(getmax(matrix1, set([]), 0))       
  30. print('cost %fs'%(time.time()-st)) #2.2s
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
197 
累计签到:231 天
连续签到:1 天
发表于 2017-10-10 12:39:29 | 显示全部楼层
@jerryxjr1220
怎么确定这个解就是最大值,如果不是全部遍历的话?

就像爬一座山,你随机跳到山腰的某个位置,然后向各个方向挪一小步,保留位置变高的变化。
如果各个方向都是变低,那现在的位置就是最高点山顶了。

点评

不,我坚决不同意楼主的看法!: 3.0
不,我坚决不同意楼主的看法!: 3
但是这个假设的前提是这个函数是单调递增或递减才有意义啊。不然最多只能说取得了局部最优解,怎么能证明是全局最优解呢?  发表于 2017-10-10 13:23
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
5 
累计签到:225 天
连续签到:118 天
发表于 2017-10-10 13:13:15 | 显示全部楼层
听取了jerryxjr1220 版主的建议,使用itertools库中的迭代器代替自己写的递归函数,效率提升不少,谢谢@jerryxjr1220 (在python浩瀚的库函数面前,永远都是孤陋寡闻),但是要计算15阶还是有困难啊


大概写个结果吧
  5阶 3315  
  6阶 4578
  7阶 5712
  8阶 7114
  9阶 7818
10阶 8779   运行时间 21秒  (有一次运行14秒)
11阶 9876   运行时间 250秒 (有一次运行173秒)
12阶 11239 运行时间 2080


# -*- coding: utf-8 -*-
"""
Created on Mon Oct  9 15:44:11 2017

"""

#读取数据文件
#数据文件存取格式为
'''
7  53 183 439 863
497 383 563  79 973
287  63 343 169 583
627 343 773 959 943
767 473 103 699 303
'''


import datetime
import itertools


starttime = datetime.datetime.now()

datafile_path="C:/E_Users/Python/fishc/data12.txt"
f = open(datafile_path)
X = f.readlines()
f.close()

#设定二维列表初值
val_2d=[1]

#将读取的字符串数据进行分割,转换为二维整型列表
index=0
for i in X:
     D  = i.split()
     val_D= [int(j) for j in D ]
     tmp=[0 for j in D]
     if(index==0):
         val_2d[0]=val_D
     else:
         val_2d.append(val_D)
     index=index+1
     
#取得二维整型列表行数和列数  (假定读取的是规则数据)     
column_val=len(val_2d)
row_val=len(val_2d[0])


#调用迭代器,取出数组每一列的组合进行相加
maxx = 0;
for each in itertools.permutations(range(row_val)):
    maxx = max(maxx, sum(val_2d[i][each[i]] for i in range(row_val)))


#long running

endtime = datetime.datetime.now()
print(maxx);

print ((endtime - starttime).seconds)

点评

我很赞同!: 5.0
我很赞同!: 5
穷举的话差不多就是这样了,除非用线性规划的方法,0.1秒就出结果,等下周看我答案揭晓吧^_^  发表于 2017-10-10 13:18
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
197 
累计签到:231 天
连续签到:1 天
发表于 2017-10-10 14:16:44 | 显示全部楼层
@jerryxjr1220
如果是非线性的,怎么能用线性规划求解呢~

蒙特卡罗算法求多解确实有局部次优解的缺点;
而模拟退火算法就是克服此缺点作的改进。

点评

我很赞同!: 5.0
我很赞同!: 5
去维基百科科普了一下,模拟退火应该是能求出全局最优解的,但是计算复杂度也不小。蒙特卡洛不能保证能求出全局最优解,但是由于有一定的运气成分(初始随机数),所以可能速度比较快。  发表于 2017-10-10 15:06
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
197 
累计签到:231 天
连续签到:1 天
发表于 2017-10-10 15:31:55 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:1 天
连续签到:1 天
发表于 2017-10-13 22:21:03 | 显示全部楼层
str = '''7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805'''
list1 = str.split()
list2 = []
for each in range(0,225,15):
    list2.append(list1[each:each+15])
out_x = []
out_y = []
postion = []
Sum = 0
for each in range(15):
    temp_x = 0
    temp_y = 0
    Max = 0
    for y,temp1 in enumerate(list2):
        for x,temp2 in enumerate(temp1):
            if Max <= int(temp2):
                if  x not in out_x and y not in out_y:
                    Max = int(temp2)
                    temp_x = x
                    temp_y = y
    Sum += Max
    out_x.append(temp_x)
    out_y.append(temp_y)
    postion.append((Max,temp_x,temp_y))
print('最大值',Sum,postion)

每次在坐标系内取最大值  记录下标  并保存  下次不再改行 该列进行挑选  保证每个数值都该行 该列是最大值

点评

不,我坚决不同意楼主的看法!: 5.0
不,我坚决不同意楼主的看法!: 5
不能只从每行或每列中选择最值。比如[ [4,3], [3,1] ]这个矩阵,按照最值选的话,肯定结果选的是(4,1),而实际(3,3)才是最大值,这说明局部最优解未必是全局最优  发表于 2017-10-16 10:48
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-10-15 20:51:28 | 显示全部楼层
本帖最后由 夏天和大熊 于 2017-10-15 21:00 编辑

        思路大概每次选中一个数后,那整个矩阵的和就减少与其相同行列数的和,以此作为权重生成一个新的矩阵,对每个数进行衡量,然后找出一个对和减少最少的。一开始思考的时候没有考虑这个数本身的值会留下来,结果就跑偏了,开始以为这个思路不对。还有个跑偏的地方是一开始用的二维列表来存储整个矩阵,也没有单独写一个矩阵的class,而造成了很多操作上的麻烦。最后发现直接存放在一个列表里进行操作也不会对判断造成影响。
        最后的结果是12690

  1. import re
  2. import time as t

  3. #将给出的数组从字符串中用正则表达式找出来
  4. def get_matrix():

  5.     num = '''7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
  6.     627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
  7.     447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
  8.     217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
  9.     960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
  10.     870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
  11.     973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
  12.     322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
  13.     445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
  14.     414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
  15.     184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
  16.     821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
  17.     34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
  18.     815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
  19.     813 883 451 509 615  77 281 613 459 205 380 274 302  35 805'''


  20.     list_str = re.findall(r'\d{1,3}', num)
  21.     list_num = []
  22.     for each in list_str:
  23.         list_num.append(int(each))

  24.     return list_num

  25. #考虑选中数后对整个矩阵所有数值和的影响,找出一个影响最小的位置(选中一个数后,和他相同行和列的数值都将从矩阵中移除)
  26. def change_matrix(matrix, len_matrix):

  27.     matrix_ins = []
  28.     sum_row = [sum(matrix[row*len_matrix : (row+1)*len_matrix]) for row in range(len_matrix)]
  29.     sum_line = [sum(matrix[line::len_matrix]) for line in range(len_matrix)]
  30.    
  31.     min_row, min_line, min_num = 0, 0, 1000*len_matrix
  32.     for row in range(len_matrix):
  33.         for line in range(len_matrix):
  34.             num_ins = sum_row[row] + sum_line[line] - 3*matrix[row*len_matrix + line]
  35.             matrix_ins.append(num_ins)
  36.             if num_ins < min_num:
  37.                 min_num = num_ins
  38.                 min_row, min_line = row, line
  39.                
  40.     return (min_row, min_line)

  41. #将被选中的行和列从从矩阵中移除,否则会影响对之后数值的判断
  42. def cut_matrix(matrix, row, line, len_mar):
  43.    
  44.     mar_c = [matrix[i] for i in range(len_mar**2) if i//len_mar != row and i%len_mar != line]

  45.     return mar_c

  46. #每次取出影响的数,然后对矩阵裁剪,直到剩下1个数为止   
  47. def sum_matrix():
  48.     matrix = get_matrix()
  49.     len_mar = int(len(matrix)**0.5)
  50.     list_sum = []
  51.     while len_mar > 1:
  52.         ram = change_matrix(matrix, len_mar)
  53.         list_sum.append(matrix[ram[0]*len_mar + ram[1]])
  54.         matrix = cut_matrix(matrix, ram[0], ram[1], len_mar)
  55.         len_mar = int(len(matrix)**0.5)
  56.     return sum(list_sum) + matrix[0]
  57.         
  58.         
  59. if __name__ == '__main__':
  60.     t_st = t.time()
  61.     print(sum_matrix())
  62.     print(t.time()- t_st)
复制代码

点评

不,我坚决不同意楼主的看法!: 5.0
不,我坚决不同意楼主的看法!: 5
不能只从每行或每列中选择最值。比如[ [4,3], [3,1] ]这个矩阵,按照最值选的话,肯定结果选的是(4,1),而实际(3,3)才是最大值,这说明局部最优解未必是全局最优   发表于 2017-10-16 10:43
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-10-24 13:43 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表