C言語　多重ループの場合のコードの書き方


下記のプログラムは、

  * `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]

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




「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]




中島さんの「組みわせ」の仕方についての質問に対する回答ではありません。  
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]

