在矩阵中找到所有可能的总和 [英] find the all possible sum in a matrix

问题描述

我正在尝试编写代码，以查找二维矩阵中所有可能数字的总和.但是要注意的是，您必须从一行中选择一个元素.

I am trying to write a code that find the sum of all the possible numbers in a 2d matrix. But the catch is that you must choose one element from one row.

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
#include <math.h>
using namespace std;
int main() { 
    int n;
    cin>>n;
    int array[n][n]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>array[i][j];
        }
    }
    int power=pow(n,n);
    int sum[power]={0};
    for(int i=0;i<power;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<n;l++){
                sum[i]=sum[i]+array[j][l];
            }
        }
    }
    for(int i=0;i<power;i++){
        cout<<sum[i]<<" ";
    }
    return 0;
}

此代码仅显示2d数组中所有元素的总和.因此，我需要帮助来尝试找到所有可能的总和，因为从每一行中为每个总和选择了一个元素.

this code only brings out the sum of all the elements in the 2d array. So i need help trying to find all the possible sum given one element from each row is chosen for each sum.

2
1 1
1 2

2, 3, 2, 3

这应该是输出，但只给出5

this should be the output but it only gives out 5

推荐答案

您的核心循环全错了.如果希望 sum [i] 包含给定路径的值，则需要将 i 当作是通过矩阵的路径.

Your core loop is all wrong. If you want sum[i] to contain the values for a given path, you need to treat i as if it were a path through the matrix.

通常，将 i 视为以n为底的数字(本例中为= 2).这意味着

In general, treat i as a number in base n (=2 for your example). That means

i = idx_1 * n ^(n-1)+ idx_2 * n ^(n-2)+ ... + idx_n

i = idx_1 * n^(n-1) + idx_2 * n^(n-2) + ... + idx_n

您可以通过重复除以n并取余数来恢复各种索引:

You can recover the various indexes by repeatedly dividing by n and taking the remainder:

for(uint64_t i=0;i<power;i++){
   sum[i] = 0;
   uint64_t encoded_index = i;
   for (size_t j = 0; j < n; j++) {
       uint64_t index_j = encoded_index % n;
       encoded_index /= n;
       sum[i] += hist[j][index_j];
   }
}

当然，只有当n * n<2 ** 64(因为uint64_t为64位).有关更一般的方法，请参阅我对其他问题的回答.

And of course this trick only works if n*n < 2**64 (as uint64_t is 64 bits). For a more general approach see my answer to your other question.

这篇关于在矩阵中找到所有可能的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！