| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 3171 人关注过本帖
标题:一个关于方阵数组取值问题~
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
结帖率:99.25%
收藏
已结贴  问题点数:100 回复次数:32 
一个关于方阵数组取值问题~
有一个由N*N个非负整数组成的方阵数组,现在规定每一行每一列只能取其中一个数,求所取的N个数的和的最小值。

输入:
第一行输入正整数N构建一个N*N的方阵
接下来有N行每行输入N个非负整数构建一个N*N的方阵

输出:输出其最小值的和。

输入:

4
1 3 5 7
1 1 3 5
3 1 1 3
5 3 1 1

输出:
4

3
1 3 4
2 2 3
3 1 2

输出:
5

虽然题目只要求计算结果,但最好按行坐标来打印出其中一种最小值的取法,例如第一个案例的取法是(1,1),(2,2),(3,3),(4,4)
第二个案例有两种取法~其中一种是(1,1),(2,2),(3,3)另外一种是(1,1),(2,3),(3,2)打印其中一种就行了~

现在除了想到全组合硬来外想不到其它更好的算法~求优化啊~
搜索更多相关主题的帖子: 最好 正整数 
2017-04-17 13:25
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:28
帖 子:1627
专家分:5219
注 册:2016-12-1
收藏
得分:2 
先占个坑。
……仔细想想先。

[此贴子已经被作者于2017-4-17 13:40编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-04-17 13:35
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 2楼 renkejun1942
一楼说错了~应该是全排列~天哪~看来穷举法不太现实耶~

好吧~谢啦~

感觉证明其最小值还是很有难度啊~很久没有遭到如此卡壳的题目了~连个除了穷举外的实现思路都没有~




[此贴子已经被作者于2017-4-17 13:45编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-17 13:43
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:371
帖 子:7412
专家分:43153
注 册:2011-1-18
收藏
得分:10 
就是一个“全排列”算法,以3*3为例
0,1,2的全排列有 {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}
举例 {1,2,0},表示 arr[0][1]+arr[1][2]+arr[2][0]

用C++写就是:
程序代码:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <numeric>
using namespace std;

int main( void )
{
    size_t n;
    cin >> n;
    vector<size_t> arr( n*n );
    copy_n( std::istream_iterator<size_t>(cin), n*n, arr.begin() );

    size_t min_sum = std::numeric_limits<size_t>::max();
    {
        vector<size_t> idx( n );
        iota( idx.begin(), idx.end(), 0 );
        do
        {
            size_t sum = 0;
            for( size_t r=0; r!=n; ++r )
                sum += arr[ r*n + idx[r] ];
            min_sum = min( min_sum, sum );
        }
        while( std::next_permutation(idx.begin(),idx.end()) );
    }
    cout << min_sum << endl;
}

2017-04-17 14:43
初学编程的人
Rank: 2
等 级:论坛游民
威 望:2
帖 子:90
专家分:84
注 册:2017-3-12
收藏
得分:0 
楼上的算法在我的笔记本上计算10*10的矩阵需要大约1分钟。12*12的我试了一下,没耐心等所以换成了10*10
2017-04-17 15:37
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:371
帖 子:7412
专家分:43153
注 册:2011-1-18
收藏
得分:10 
以下是引用初学编程的人在2017-4-17 15:37:58的发言:

楼上的算法在我的笔记本上计算10*10的矩阵需要大约1分钟。12*12的我试了一下,没耐心等所以换成了10*10
时间越来越长是肯定的,T(n)耗时是T(n-1)的n

我用gcc 6.3.0试了一下,
debug下:10*10耗时  0.909287秒;release下差不多
debug下:11*11耗时  9.702019秒;release下差不多
debug下:12*12耗时118.991265秒;release下差不多
我怀疑你用的编译器在debug下加了太多的调试信息。

算法是没优化(sum不需要从头开始计算),但即使优化,也不会有数量级的差距
程序代码:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <numeric>
using namespace std;

#include <chrono>

int main( void )
{
    size_t n;
    cin >> n;
    vector<size_t> arr( n*n );
    copy_n( std::istream_iterator<size_t>(cin), n*n, arr.begin() );

std::chrono::time_point<std::chrono::steady_clock> now = std::chrono::steady_clock::now();

    size_t min_sum = std::numeric_limits<size_t>::max();
    {
        vector<size_t> idx( n );
        iota( idx.begin(), idx.end(), 0 );
        do
        {
            size_t sum = 0;
            for( size_t r=0; r!=n; ++r )
                sum += arr[ r*n + idx[r] ];
            min_sum = min( min_sum, sum );
        }
        while( std::next_permutation(idx.begin(),idx.end()) );
    }

std::chrono::time_point<std::chrono::steady_clock> cur = std::chrono::steady_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>(cur-now).count() << std::endl;

    cout << min_sum << endl;

}

2017-04-17 16:04
初学编程的人
Rank: 2
等 级:论坛游民
威 望:2
帖 子:90
专家分:84
注 册:2017-3-12
收藏
得分:1 
回复 6楼 rjsp
我在powershell里面运行的,所以非常慢

错了,编辑掉

[此贴子已经被作者于2017-4-17 16:55编辑过]

2017-04-17 16:06
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 4楼 rjsp
我用C-Free运行了一下发现有不支持的地方
 error: `copy_n' was not declared in this scope
 error: `iota' was not declared in this scope

想到了如果当前解如果为最优解则无论交换任意两个取法的值都会比原来的要大~此时就可以结束循环了~不一定要算所有排列~
如果这条题实在优化不了就用全排列思路吧~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-17 17:18
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
收藏
得分:2 
一回来就出道这么难的题。算法真不好设计
2017-04-17 18:29
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 9楼 yangfrancis
全排列穷举不难~难在优化~
想到了一些优化方法~就是当是最优解时无论交换任意两个数的和都会增大~这样判断次是数不稳定的~

一个数变换最小值状态可以考虑每次对齐一个数位这样最多交换N-1次~应该尽量避免交换过程中同一个数出现在相同的位置~想到了用逐步趋近最优状态的方法来求这个最小值~这和广搜有点关系……但算法复杂度似乎很高~而且这个方法的可行性还没有很大把握~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-17 19:02
快速回复:一个关于方阵数组取值问题~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.060405 second(s), 8 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved