59544


下記のプログラムは、

  * `sum`円の所持金があり、`n`種類の商品の中から`cnt`個の商品を選びお釣り(`min`円)を最小にする

というアルゴリズムです（商品は安い順に`x[1]`円,`x[2]`円,,,,`x[n]`円と示されます）

現状では、下記のコードのとおり、回文の中に回文といった構造になっており、`cnt`の値によってループの数やループの条件が変わっていくようになっております。

`cnt`の値は入力値で与えられるため、どの`cnt`の値にも対応可能な式を作りたいのですが、どのようにすればいいのでしょうか？

[code]

    // cnt=2の場合
    int min=10000001;
    for(int k=n;sum>=x[k]&&k>=cnt;k--){
        for(int j=k-1;sum>=x[k]+x[j]&&j>=cnt-1;j--){
            min=min>(sum-x[k]-x[j])?(sum-x[k]-x[j]):min;
        }
    }
    
[/code]

と

[code]

    // cnt=4の場合
    int min=10000001;
    for(int k=n;sum>=x[k]&&k>=cnt;k--){
           for(int j=k-1;sum>=x[k]+x[j]&&j>=cnt-1;j--){
               for(int i=j-1;sum>=x[k]+x[j]+x[i]&&i>=cnt-2;i--){
                   for(int l=i-1;sum>=x[k]+x[j]+x[i]+x[l]&&l>=cnt-3;l--){
                           min=min>(sum-x[k]-x[j]-x[i]-x[l])?(sum-x[k]-x[j]-x[i]-x[l]):min;
                   }
               }
           }
       }
    
[/code]

✳︎初心者であるため、適切でない表現が含まれていますがご了承ください


CC BY-SA 4.0
2019-10-05T09:13:23.610
59481
2019-10-07T22:48:58.007
2019-10-05T14:47:24.557
34550
34550
question
c
C言語　多重ループの場合のコードの書き方


現在のご質問文中で「回文の中に回文といった構造」と言うのは、  
こんな構造↓

[code]

    for(...) {
        for(...) {
            for(...) {
                for(...) {
                    ...
                }
            }
        }
    }
    
[/code]

を表すのに言い得て妙と言う気はするのですが、やはりプログラミングの世界では「入れ子」とか「ネスト」なんて定着した言葉があるので、そちらを使っていただいた方がより多くの人に早く意図を伝えられるかと思います。(「入れ子」の実物なんて、私がプログラミングの学習を始めた頃(戦後です、一応)から見られなかったものなので、適切な用語かどうかは疑問ですが。)

あなたのご質問をプログラミング業界で通じる普通の言い回しにすると「普通に総当たりの解法をfor文の入れ子で表現すると、パラメータ`cnt`の値に応じた深さの入れ子にしないといけないが、`cnt`の値によらず解けるようなコードにしたい」と言った感じになるでしょうか。

このような問題を解くには「再帰」を使うのが極めて自然でわかりやすくなるのですが、ここではあえて再帰を使わない解答例を挙げておきます。

「元の問題を一般的に解くのは難しいが、(元の問題を解くのに必要な)全ての組み合わせを作るだけなら、再帰を使わなくてもかけそう」と言った場合に使える手法です。

基本はこんな感じ。

[code]

        「組み合わせ」を初期化;
        do {
            取得した「組み合わせ」であれこれ;
        } while( 次の「組み合わせ」を求める );
    
[/code]

と言う感じで、総当たりの問題は、ネストされたfor文を使わなくても、一重のループに書き直すことができます。問題の種類によっては『次の「組み合わせ」を求める』部分が極端に複雑になってしまうのですが。

* * *

とりあえず、あなたの課題を上記の方針で書いてみるとこんな感じ。

[code]

    #include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    int maxTotal(int cnt, int limit);
    void initSeq(int *seq, int cnt);
    int sumSeq(int *seq, int cnt);
    bool nextSeq(int *seq, int cnt);
    void printSeq(int *seq, int cnt);
    
    int main(int argc, const char * argv[]) {
        printf("%d\n", maxTotal(4, 1000));
        return 0;
    }
    
    //商品の価格は安い順にx[0]からx[n-1]の順に入っている
    int x[] = {43, 213, 283, 335, 337, 429, 643, 745, 828, 861};
    //商品の種類(出題の`n`)
    #define XCOUNT 10
    
    //中で合計を求めないといけないので、所持金は`sum`ではなく`limit`としている
    int maxTotal(int cnt, int limit) {
        //「お釣りの額を最小」ではなく、「(制限値内で)使う金額を最大」と考える
        int maxSum = INT_MIN;
        int *seq = (int *)calloc(cnt, sizeof(int));
        initSeq(seq, cnt);
        do {
            printSeq(seq, cnt);
            int sum = sumSeq(seq, cnt);
            if( sum <= limit && sum > maxSum) {
                maxSum = sum;
            }
        } while( nextSeq(seq, cnt) );
        return maxSum;
    }
    
    //「組み合わせ」の初期化
    void initSeq(int *seq, int cnt) {
        for( int i = 0; i < cnt; ++i ) {
            seq[i] = XCOUNT - 1 - i;
        }
    }
    
    //現在の「組み合わせ」での合計を求める
    int sumSeq(int *seq, int cnt) {
        int sum = 0;
        for( int i = 0; i < cnt; ++i ) {
            sum += x[seq[i]];
        }
        return sum;
    }
    
    //次の「組み合わせ」を求める
    bool nextSeq(int *seq, int cnt) {
        for( int i = cnt - 1; i >= 0; --i ) {
            if( seq[i] > 0 ) {
                seq[i] -= 1;
                bool finished = true;
                for( int j = i+1; j < cnt; ++j ) {
                    if( seq[j-1] == 0 ) {
                        finished = false;
                        break;
                    }
                    seq[j] = seq[j-1] - 1;
                }
                if( finished ) {
                    return true;
                }
            }
        }
        return false;
    }
    
    //「組み合わせ」の表示(デバッグ用)
    void printSeq(int *seq, int cnt) {
        printf("[");
        for( int i = 0; i < cnt; ++i ) {
            printf("%d", seq[i]);
            if( i < cnt - 1 ) {
                printf(", ");
            }
        }
        printf("]\n");
    }
    
[/code]

(stdbool.hなんかが使えない古いCだと修正が必要になります。K&Rスタイルの古いCを学習した人にチェックされるとダメ出しを食らうような部分があるかもしれません。)

ただし、プログラミングチャレンジの出題のような場合、「単純な総当たり」では時間切れになってしまうような設定になっていることが多いです。上記のように「組み合わせ」だけを別途求めるようにすると、単純な枝刈りさえ難しくなるので、あまりお勧めはしにくい解き方ということになります。


CC BY-SA 4.0
2019-10-05T17:17:39.317
59488
2019-10-05T17:17:39.317
13972
59481
answer


中島さんの「組みわせ」の仕方についての質問に対する回答ではありません。  
for文の入れ子を再帰で表すコードの例です。

繰り返される処理はfunc()です。  
このコード例では  
・次元数はi_level_num  
・多次元配列の添え字がai_idxで渡されます。  
サンプルのfunc()は各次元の添え字を出力しているだけです。

main()では以下を行っています。  
・３次元[3][4][5]のループでfunc()を呼び出す  
・４次元[5][4][3][2]のループでfunc()を呼び出す

【ソースコードサンプル】

[code]

    #include <stdio.h>
    int func(int i_level_num, int ai_idx[]);
    int func(int i_level_num, int ai_idx[])
    {
        int i;
        printf("ai_idx");
        for(i = 0; i < i_level_num; i++){
            printf("[%d]", ai_idx[i]);
        }
        printf("\n");
        return 0;
    }
    
    int looploop(int ai_level[], int i_level_num, int i_level, int ai_idx[], int (*pfunc)(int i_level_num, int ai_idx[]));
    int looploop(int ai_level[], int i_level_num, int i_level, int ai_idx[], int (*pfunc)(int i_level_num, int ai_idx[]))
    {
        int i;
        if( i_level >= i_level_num){
            pfunc(i_level_num, ai_idx);
            return 0;
        }
        for( i = 0; i < ai_level[i_level]; i++){
            ai_idx[i_level] =  i;
            looploop(ai_level, i_level_num, i_level + 1, ai_idx, pfunc);
        }
        return 0;
    }
    #define ELEMENT_NUM(A) (sizeof(A)/sizeof(A[0]))
    int main(int argc, char *argv[])
    {
        int ai_level_3[] = {3,4,5};
        int ai_idx_3[ELEMENT_NUM(ai_level_3)];
        printf("3重ループ[3][4][5]\n");
        looploop(ai_level_3, ELEMENT_NUM(ai_level_3), 0, ai_idx_3, func);
    
        int ai_level_4[] = {5,4,3,2};
        int ai_idx_4[ELEMENT_NUM(ai_level_4)];
        printf("4重ループ[5][4][3][2]\n");
        looploop(ai_level_4, ELEMENT_NUM(ai_level_4), 0, ai_idx_4, func);
        return 0;
    }
    
    
[/code]

【実行結果】

[code]

    3重ループ[3][4][5]
    ai_idx[0][0][0]
    ai_idx[0][0][1]
    ai_idx[0][0][2]
    ai_idx[0][0][3]
    ai_idx[0][0][4]
    ai_idx[0][1][0]
    ai_idx[0][1][1]
    ai_idx[0][1][2]
    ai_idx[0][1][3]
    ai_idx[0][1][4]
    ai_idx[0][2][0]
    ai_idx[0][2][1]
    ai_idx[0][2][2]
    ai_idx[0][2][3]
    ai_idx[0][2][4]
    ai_idx[0][3][0]
    ai_idx[0][3][1]
    ai_idx[0][3][2]
    ai_idx[0][3][3]
    ai_idx[0][3][4]
    ai_idx[1][0][0]
    ai_idx[1][0][1]
    ai_idx[1][0][2]
    ai_idx[1][0][3]
    ai_idx[1][0][4]
    ai_idx[1][1][0]
    ai_idx[1][1][1]
    ai_idx[1][1][2]
    ai_idx[1][1][3]
    ai_idx[1][1][4]
    ai_idx[1][2][0]
    ai_idx[1][2][1]
    ai_idx[1][2][2]
    ai_idx[1][2][3]
    ai_idx[1][2][4]
    ai_idx[1][3][0]
    ai_idx[1][3][1]
    ai_idx[1][3][2]
    ai_idx[1][3][3]
    ai_idx[1][3][4]
    ai_idx[2][0][0]
    ai_idx[2][0][1]
    ai_idx[2][0][2]
    ai_idx[2][0][3]
    ai_idx[2][0][4]
    ai_idx[2][1][0]
    ai_idx[2][1][1]
    ai_idx[2][1][2]
    ai_idx[2][1][3]
    ai_idx[2][1][4]
    ai_idx[2][2][0]
    ai_idx[2][2][1]
    ai_idx[2][2][2]
    ai_idx[2][2][3]
    ai_idx[2][2][4]
    ai_idx[2][3][0]
    ai_idx[2][3][1]
    ai_idx[2][3][2]
    ai_idx[2][3][3]
    ai_idx[2][3][4]
    4重ループ[5][4][3][2]
    ai_idx[0][0][0][0]
    ai_idx[0][0][0][1]
    ai_idx[0][0][1][0]
    ai_idx[0][0][1][1]
    ai_idx[0][0][2][0]
    ai_idx[0][0][2][1]
    ai_idx[0][1][0][0]
    ai_idx[0][1][0][1]
    ai_idx[0][1][1][0]
    ai_idx[0][1][1][1]
    ai_idx[0][1][2][0]
    ai_idx[0][1][2][1]
    ai_idx[0][2][0][0]
    ai_idx[0][2][0][1]
    ai_idx[0][2][1][0]
    ai_idx[0][2][1][1]
    ai_idx[0][2][2][0]
    ai_idx[0][2][2][1]
    ai_idx[0][3][0][0]
    ai_idx[0][3][0][1]
    ai_idx[0][3][1][0]
    ai_idx[0][3][1][1]
    ai_idx[0][3][2][0]
    ai_idx[0][3][2][1]
    ai_idx[1][0][0][0]
    ai_idx[1][0][0][1]
    ai_idx[1][0][1][0]
    ai_idx[1][0][1][1]
    ai_idx[1][0][2][0]
    ai_idx[1][0][2][1]
    ai_idx[1][1][0][0]
    ai_idx[1][1][0][1]
    ai_idx[1][1][1][0]
    ai_idx[1][1][1][1]
    ai_idx[1][1][2][0]
    ai_idx[1][1][2][1]
    ai_idx[1][2][0][0]
    ai_idx[1][2][0][1]
    ai_idx[1][2][1][0]
    ai_idx[1][2][1][1]
    ai_idx[1][2][2][0]
    ai_idx[1][2][2][1]
    ai_idx[1][3][0][0]
    ai_idx[1][3][0][1]
    ai_idx[1][3][1][0]
    ai_idx[1][3][1][1]
    ai_idx[1][3][2][0]
    ai_idx[1][3][2][1]
    ai_idx[2][0][0][0]
    ai_idx[2][0][0][1]
    ai_idx[2][0][1][0]
    ai_idx[2][0][1][1]
    ai_idx[2][0][2][0]
    ai_idx[2][0][2][1]
    ai_idx[2][1][0][0]
    ai_idx[2][1][0][1]
    ai_idx[2][1][1][0]
    ai_idx[2][1][1][1]
    ai_idx[2][1][2][0]
    ai_idx[2][1][2][1]
    ai_idx[2][2][0][0]
    ai_idx[2][2][0][1]
    ai_idx[2][2][1][0]
    ai_idx[2][2][1][1]
    ai_idx[2][2][2][0]
    ai_idx[2][2][2][1]
    ai_idx[2][3][0][0]
    ai_idx[2][3][0][1]
    ai_idx[2][3][1][0]
    ai_idx[2][3][1][1]
    ai_idx[2][3][2][0]
    ai_idx[2][3][2][1]
    ai_idx[3][0][0][0]
    ai_idx[3][0][0][1]
    ai_idx[3][0][1][0]
    ai_idx[3][0][1][1]
    ai_idx[3][0][2][0]
    ai_idx[3][0][2][1]
    ai_idx[3][1][0][0]
    ai_idx[3][1][0][1]
    ai_idx[3][1][1][0]
    ai_idx[3][1][1][1]
    ai_idx[3][1][2][0]
    ai_idx[3][1][2][1]
    ai_idx[3][2][0][0]
    ai_idx[3][2][0][1]
    ai_idx[3][2][1][0]
    ai_idx[3][2][1][1]
    ai_idx[3][2][2][0]
    ai_idx[3][2][2][1]
    ai_idx[3][3][0][0]
    ai_idx[3][3][0][1]
    ai_idx[3][3][1][0]
    ai_idx[3][3][1][1]
    ai_idx[3][3][2][0]
    ai_idx[3][3][2][1]
    ai_idx[4][0][0][0]
    ai_idx[4][0][0][1]
    ai_idx[4][0][1][0]
    ai_idx[4][0][1][1]
    ai_idx[4][0][2][0]
    ai_idx[4][0][2][1]
    ai_idx[4][1][0][0]
    ai_idx[4][1][0][1]
    ai_idx[4][1][1][0]
    ai_idx[4][1][1][1]
    ai_idx[4][1][2][0]
    ai_idx[4][1][2][1]
    ai_idx[4][2][0][0]
    ai_idx[4][2][0][1]
    ai_idx[4][2][1][0]
    ai_idx[4][2][1][1]
    ai_idx[4][2][2][0]
    ai_idx[4][2][2][1]
    ai_idx[4][3][0][0]
    ai_idx[4][3][0][1]
    ai_idx[4][3][1][0]
    ai_idx[4][3][1][1]
    ai_idx[4][3][2][0]
    ai_idx[4][3][2][1]
    
    
[/code]


CC BY-SA 4.0
2019-10-07T11:49:34.647
59532
2019-10-07T12:22:50.013
2019-10-07T12:22:50.013
35558
35558
59481
answer


「for文の入れ子を再帰で表すコードの例」が投稿されましたので、元の課題を再帰で解く場合のコードを示しておきます。詳細はコメントを参照してください。

また、別解の`printSeq`相当の情報が出力できませんが、akira ejiri さんの回答を参考にすれば改善できるでしょう。

[code]

    #include <stdio.h>
    
    int maxTotalR(int n, int cnt, int limit);
    
    //商品の価格は安い順にx[0]からx[n-1]の順に入っている
    int x[] = {43, 213, 283, 335, 337, 429, 643, 745, 828, 861};
    //商品の種類(出題の`n`)
    #define XCOUNT 10
    
    int main(int argc, const char * argv[]) {
        printf("%d\n", maxTotalR(XCOUNT, 4, 1000));
        return 0;
    }
    
    // n: 商品の範囲、x[0]...x[n-1]の中から選ぶ
    // cnt: 残りの個数
    // limit: 残りの使える金額
    int maxTotalR(int n, int cnt, int limit) {
        //終了条件判定、残り0個ってことは合計金額は0円で決定
        if( cnt == 0 ) {
            return 0;
        }
        //自明なケースを早めに刈ることで組み合わせの総数を減らす
        if( cnt > n ) {
            return -1;
        }
        //最大値を求めるため&&有効な値がなければ-1を返すための初期化
        int maxSum = -1;
        for( int i = n - 1; i >= 0; --i ) {
            //再帰呼び出しの時は確実にcntの値を減らしていることに注意、この結果cnt==0が有効な終了条件として働く
            int subsum = maxTotalR(i, cnt - 1, limit - x[i]);
            //subsum<0は解なしを表しているので、subsum>=0の時にだけ合計を求める
            if( subsum >= 0 ) {
                int sum = x[i] + subsum;
                if( sum <= limit && sum > maxSum ) {
                    maxSum = sum;
                }
            }
        }
        return maxSum;
    }
    
[/code]


CC BY-SA 4.0
2019-10-07T22:48:58.007
59544
2019-10-07T22:48:58.007
13972
59481
answer