[算法] 贪心--矩阵消除游戏

今天咱们来分享一道基础的贪心题目 -> 矩阵消除游戏

  对于贪心算法的题目, 我感觉是对于初学者没必要太注重证明过程, 因为这玩意的变数比较大, 还是应该关注在编码和思路上, 在思路上对了就行.

1. 题意

题目描述
  牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n{n}行m{m}列，第i{i}行第j{j}列的单元格的权值为ai,ja_{i,j}，牛妹可以进行k{k}个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0{0}，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。
牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:
第一行三个整数n,m,k{n,m,k}
接下来n{n}行每行m{m}个整数表示矩阵中各个单元格的权值。

输出描述:
输出一个整数表示牛妹能获得的最大分数。

示例1
输入

输出
414

备注:

2. 思路

贪心思路1

  思路1: 这个题目一上来如果盲才的话, 直觉上是统计一下每行之和和每列之和, 然后找出最大的数来, 加到ret上, 然后把对应的数变成0, 再找出第二大的列和/行和, 以此重复操作, 直到k次/该数组所有行列已经被全部清0.
  我们以示例1举个例子(最下一行为每列的和, 最右边一列为每行之和):

然后, 我们第一步选211对吧? ret += 211然后就会变成下面:

然后我们再选203, ret += 204, ret = 414, 我们可以看到:

总共选择了两次, 因此我们的结果就是414.

思路1并不正确

显然, 这个思路1并不正确, 因为我们可以轻松举出反例: 其中k = 2

如果按照贪心来求, 会先选择100 + 100, 然后清零操作:

然后再选择 9 + 1

所以贪心求出来的结果是多少呢? 210.
但是如果我们直接找的是第一行和第三行呢? sum = 218.

因此, 我们上面的贪心解是错误的!

思路1为什么是错误的?

  我们继续以我们举的反例来说, 只能说是因为贪心算法目光短视并且第一步选啥会对第二步所选产生影响所导致的!

为什么思路1是错误的?

• 因为贪心是目光狭隘的, 只看得到当前这一步.
• 因为这个题目行会影响列, 列会影响行, 行列之间强关联.

这道题该如何求解?

  我们的思路1只能说不是完全对, 但是针对大部分情况是对的, 关键问题在于行列之间强关联 + 贪心算法鼠目寸光, 所以, 我们需要使行列解耦合.

如何解耦合??? -> 很简单, 枚举啊!

枚举思路是超时的!

  如果用暴力求解: 假设n和m都不大，比如都是20左右，那么总共有40个元素（行+列），每个可以选择或不选，但总选择的数量不超过k。这时候，枚举所有可能的组合，总共有C(40,0)+C(40,1)+…+C(40,k)种可能。当k=20时，这大约是组合数的总和，可能达到1e12，这显然不可行。

  显然, 这样去做的话可以解耦, 因为行和列的关系从暴力的角度来说就不存在啥制约关系了, 因为所有可能情况我们都会计算嘛, 压根就不会担心选哪行哪列的问题! 但是缺点是时间复杂度上来了!

  那我们可不可以有一种算法比思路1效率上差点, 但是可以解除行列耦合, 比暴力效率高点呢? 我们尝试把这两种思路结合一下:

枚举 + 贪心

  既然⾏的选择会影响列，那我们⼲脆直接把「所有⾏的选法」枚举出来，然后针对「每⼀种⾏的选法」再处理列，这样就会把「所有情况」都考虑进去。
因此，最优解是先暴⼒枚举所有⾏的选法，在⾏的选择都确定之后，再去贪⼼的处理列。

  这样的话, 因为我们枚举了行, 针对每一种行的情况, 贪心只需要贪列的部分就可以了, 因此行列就不会影响贪心选择了, 而且效率上, 因为列的部分是贪心出来的, 所以效率上也得到了提高!

3. 编码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n, m, k;
const int N = 20;
int nums[N][N];
int col[N];

bool cmp(int a, int b)
{
    return a > b;
}

int calc(int x)
{
    int ret = 0;
    while(x)
    {
        ret += 1;
        x -= (x & -x);
    }
    
    return ret;
}

int main()
{
    int ret = 0;
    // 读入数据
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> nums[i][j];
    
    // 二进制枚举
    for(int stat = 0; stat < (1 << n); stat++)
    {
        int size = calc(stat);
        if(size > k) continue;
        memset(col, 0, sizeof col);
        
        // 合法, 我们统计一下行的和, 统计一下列的情况
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(stat & (1 << i)) sum += nums[i][j];
                else col[j] += nums[i][j];
            }
        }
        
        sort(col, col + m, cmp);
        int take = min(k - size, m); // [细节]: 有没有可能k - size > m呢? 也就是会越界访问??? 
        for(int i = 0; i < take; i++) 
            sum += col[i];
        ret = max(ret, sum);
    }
    
    cout << ret << endl;
    
    return 0;
}

编码细节: 如果k > m + n, 则可能会导致贪心算法加和的时候会越界, 因此我们需要额外判断一下!