0

最近、私はパーティションの問題に取り組んでいます。調査を行ったところ、Wiki ページのアルゴリズムを使用して解決できることがわかりました。疑似アルゴリズムは次のとおりです。

   INPUT:  A list of integers S
   OUTPUT: True if S can be partitioned into two subsets that have equal sum
1 function find_partition( S ):
2     N ← sum(S)
3     P ← empty boolean table of size (\lfloor N/2 \rfloor  +  1) by (n + 1)
4     initialize top row (P(0,x)) of P to True
5     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
6     for i from 1 to \lfloor N/2 \rfloor 
7          for j from 1 to n
8          P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1)
9     return P(\lfloor N/2 \rfloor , n)

再帰を使用すると、配列内の整数から特定の合計に到達できるかどうかを計算できます。到達できる場合は true を返します。解決策が見つかるまで、最初sumOfTheIntegers/2から 0 に戻ります。平均以下の整数の可能な最大の合計を見つけたら、 を使用して 2 つの整数グループの差を計算し(average-lowestSumLowerorEqualtoAverage)*2ます。

しかし、再帰に1次元配列を含めるにはどうすればよいですか?

これがコードです。おそらく動作するはずですが、問題があるため、まだテストしていません。そのため、コードに小さなエラーが含まれている可能性があります。しかし、それは問題ではありません。後で修正します。

#include <iostream>
#include <cmath>
using namespace std;
bool matrix (int a, int b)
{
    if(b == -1)  return true;
    else if (a == -1) return false;
    else if(matrix(a-1, b) == true) return true;
    else if(matrix(a-1,b-numbers[a-1]) == true) return true;
    else return false;
}
int main()
{
    int number, sum = 0;
    cin >> number;
    int numbers[number];
    for(int i = 0; i<number; i++)
    {
        cin >> numbers[i];
        sum += numbers[i];
    }
    double average = sum/2.0;
    for(int i = floor(sum/2); i!= 0; i--)
    {
        if(matrix(number+1, i) == true)
        {
            cout << abs(average-i)*2;
            break;
        }
    }
    return 0;
}
4

2 に答える 2

1

最も簡単な (ただし最善ではない) 方法は、グローバル変数を導入することです。

#include <vector>
std::vector<int> numbers;

/* ... */

int main(){
    int number;
    cin >> number;
    numbers.resize(number);
    /* ... */
}

もう 1 つの可能性は、追加のパラメーターを使用することです。

bool matrix (int a, int b, const std::vector<int>& numbers)
{
    if(b == -1)  return true;
    else if (a == -1) return false;
    else if(matrix(a-1, b,numbers) == true) return true;
    else if(matrix(a-1,b-numbers[a-1],numbers) == true) return true;
    else return false;
}

int numbers[number]は実際にはコンパイラ固有の拡張機能 (VLA) を使用しており、C++ 標準の一部ではないことに注意してください( 「C++ は可変長配列をサポートしていますか?」および​​「可変長配列が C++ 標準の一部ではないのはなぜですか?」を参照してください)。

于 2013-03-08T22:49:57.437 に答える
0

関数に引数として渡す

bool matrix (int a, int b, int num_arr[])
{
  ...
  matrix(a-1,b,num_arr);
  ... 
}
于 2013-03-08T22:47:49.383 に答える