-1

目標値と一連の値のリストを受け取るプログラムを作成しています。目標値に加算されるリストから数値を選択する必要があります。

これはすべてコマンドラインで行う必要があります。

私は2つの部分で立ち往生しています：

1 つ目は、すべての値を正しく読み込んでいるかどうか 100% 確信が持てないことです。一致するべきではない一部のテストでは、一致があると表示されるためです。

たとえば、subset2 100 1 2 3 4 組み合わせ一致が見つかりました

代わりに、1,2,3,4 の合計が 100 にならないため、一致が見つかりませんでした。何をしているかを確認できるようにコードを追加しました。

次に、ターゲット値と一致するリスト内の数値を出力する必要があります。どうすればそれができるのでしょうか、どうすればこれができるのか困っています。

たとえば、サブセット 9 1 2 4 5 {4,5}

#include <stdio.h>
#include <stdbool.h>

bool subset(int set[], int n, int sum);

int main(int argc, char *argv[])
{
    int value = atoi(argv[1]);

    // Error checking to see if the value is a negative
    if (value <= 0) {
        printf("Parameter 1 can not be negative\n");
        return -1;
    }

    int k;
    int t = 0;

    for (k = 2; k < argc; k++) {
        t++;
    }

    int i;
    int array = 0;

    /*
     * Putting the elements from the command line in an array starting
     * from the second element on the command line
     */

    for (i = 2; i < t; i++) {
        array += atoi(argv[i]);
    }

    int set[array];
    int n = sizeof(set) / sizeof(set[0]);

    // Call subset to check and see if there is a match
    if (subset(set, n, value) == true) {
        printf("Combination Match Found\n");
    } else {
        printf("No Combination Matches\n");
    }

    return 0;
}

// Returns true if there is a subset that equals the value
bool subset(int set[], int n, int sum)
{
    // Base cases
    if (sum == 0)
        return true;

    if (n == 0 && sum != 0)
        return false;

    // If last element is greater than sum, then its ignored
    if (set[n - 1] > sum)
        return (subset, n - 1, sum);

    // Check if value can be found with or without last element
    return subset(set, n - 1, sum) || subset(set, n - 1, sum - set[n - 1]);
}
4

2 に答える 2

0 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool subset(int set[], int n, int sum);

int main(int argc, char *argv[]){
    int value = atoi(argv[1]);

    if (value <= 0) {
        printf("Parameter 1 must be positive\n");
        return -1;
    }

    int array_size = argc - 2;
    int set[array_size];
    for(int i=0;i<array_size;++i)
        set[i] = atoi(argv[2 + i]);

    // Call subset to check and see if there is a match
    if (subset(set, array_size, value) == true) {
        printf("Combination Match Found\n");
    } else {
        printf("No Combination Matches\n");
    }

    return 0;
}

// Returns true if there is a subset that equals the value
bool subset(int set[], int n, int target_sum){
    if (target_sum == 0){
        printf("{ }\n");
        return true;
    }
    if (n == 0 && target_sum != 0)
        return false;

    unsigned limit = 1 << n;
    int wk[n];
    for(unsigned i=1;i < limit; ++i){
        int k = 0, sum = 0;
        unsigned x = i;
        for(int j = 0; x ; ++j, x>>=1){
            if(x & 1){
                sum += (wk[k++] = set[j]);
                if(sum  > target_sum) break;
            }
        }
        if(sum == target_sum){
            printf("{ ");
            for(int j = 0;j<k;++j)
                printf("%d ", wk[j]);
            printf("}\n");
            return true;
        }
    }
    return false;
}
于 2013-05-23T23:34:58.270 に答える
0

私はあなたがいたるところにいるのではないかと心配しています。最初にいくつかの小さな問題に対処します。

int value = atoi(argv[1]);

コマンド ラインに引数を指定しないとクラッシュします。argc > 1最初に確認する必要があります。

for (k = 2; k < argc; k++) {
    t++;
}

書かれていたかもしれない

t = argc - 2;

set[]の初期化に関して：

for (i = 2; i < t; i++) {
    array += atoi(argv[i]);
}

になるはずだった

for (i=0; i<t; ++i) {
    set[i] = atoi(argv[i+2]));
}

set[]は入力の配列ですよね？長さは、コマンドラインからの引数の数でなければなりませんよね? 私がその権利を読んでいる場合、setのサイズはarrayではなくtである必要があります。実際、計算後にtをどこでも使用しているとは思いません。配列は入力値の合計です。それはあなたにとっても役に立ちますか（問題が解決可能かどうかを確認するための予備的なチェックとしては別として）？

テストして可能かどうかを確認するのではなく、実際に結果を出力したい場合は、結果に配列を割り当てて、subset()に大幅な変更を加える必要があります。

set[]と同じ長さのresult[]という名前の別の配列を作成します。結果[]へのポインタを、すでに入力されている値の数 (初期値 0) とともに、subset()に渡します。subset()では、有効な値である可能性のあるset[]の値がある場合はいつでも、それをresult[]に追加し、長さをインクリメントします。同様に、subset()から戻る前に長さを減らして、中間値を効果的に削除します。subset()が、合計すると目標値になる正当な値の組み合わせがあると判断すると、その値のリストがresult[]に配置されます。.

これは宿題ですか？もしそうなら、私はあなたのために実際のコードを書くのは嫌ですが、上記の私の説明が役に立てば幸いです.

最後に -- これは少し高度な話ですが --この種の問題の最適化として、メモ化と動的プログラミングについて少し調べてみるとよいでしょう。

于 2013-05-23T20:59:56.797 に答える