24H免费课程咨询  TEL:13401595960   QQ:1870218756  微信:13401595960(李老师)

东方博宜

网站首页 > 软件开发资讯 > Java开发

【常州java培训机构】关于矩阵的算法设计

2018-02-26 10:47:21 东方博宜 阅读

问题:

N*N的矩阵,其元素不是0就是1,无规律。需求就是从这个矩阵里找出若干行,组成一个新的矩阵。这个新的矩阵在每一列上都至少要有一个1。所用行数最少的解是最优解。



解决方法:

在开始之前,先把所有行的每一列相加,找到和最小那一列,记录这一列值为1的行,作为必选行
穷举法:
1、定义选取的行数 i,从1开始,到N结束;如i=2,代表从N行中选取2行;
2、从N行中选取i行(共C(N,i)种情况),将选中的行的每列做或操作,看结果是否全为1;如果全为1,程序结束,选中的行就是结果;
3、如果i>N,程序结束,没有满足条件的结果

Powered by 东方博宜教育咨询江苏有限公司  ©2008-2018 www.czos.cn