2

下記のプログラムは、

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

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

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

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

// 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;
    }
}

// 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;
               }
           }
       }
   }

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

8
  • 1
    「多重ループを一つの式にまとめる」と言うのはどのようなことを表しているのでしょうか? 具体的な例を示してもらえないでしょうか。なにをしたいのかよくわからないので、「どのようにすればよいでしょうか?」と聞かれても答えに困ってしまいます。
    – OOPer
    Commented 2019年10月5日 9:24
  • C言語としてのコメントで、1行だけなら // を使いましょう。/* を使われていますが、閉じるための */ が抜けています。 / 「n個の商品」は個数でなく「種類」なら cnt と紛らわしくなるので注意した方がよさそうです。
    – cubick
    Commented 2019年10月5日 9:30
  • ご指摘ありがとうございます。編集いたしました。 Commented 2019年10月5日 9:38
  • 2
    ご編集いただいたのですが、やはり「統合式」のような意味のよくわからない単語が使われています。正確な用語が使えなければ質問しちゃいけないと言うつもりは全然ないんですが、やはりご質問の意図が読む側に伝わないと的確な回答は得にくいかと思います。具体例の形で示していただくことで、そこらへんが少々曖昧でも通じる場合があるかと思います。多重ループの場合でなくても良いので、是非具体例をお示しください。
    – OOPer
    Commented 2019年10月5日 9:55
  • @中島啓介 さん、cnt も入力として与えられる問題を解こうとしていて、今思いついている解き方だと cnt が固定であればその数だけ for をネストさせれば解けるのだけど、cnt が任意に与えられた場合の解き方が分からない、ということでしょうか?
    – nekketsuuu
    Commented 2019年10月5日 10:13

3 件の回答 3

2

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

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

#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;
}
2

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

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

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

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

#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;
}

【実行結果】

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]

0

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

for(...) {
    for(...) {
        for(...) {
            for(...) {
                ...
            }
        }
    }
}

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

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

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

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

基本はこんな感じ。

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

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


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

#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");
}

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

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

3
  • 丁寧なご説明ありがとうございます。総当たり問題のループ方法について具体的な理解をすることができました。さらに理解を深めたいのですが、for文の入れ子を再帰で表すとどのようなコードになるのでしょうか? Commented 2019年10月6日 10:08
  • @中島啓介 さん、このような組み合わせの総当たり問題は木構造の深さ優先探索と等価になります。「組み合わせ 深さ優先探索 再帰」辺りで検索されると色々な記事が出てきますから、直接この問題のコードを求められる前に、まずはそう言った記事を参考にして、ご自身で単純な例を書いてみることお勧めします。
    – OOPer
    Commented 2019年10月6日 11:37
  • ありがとうございます。調べてみます。 Commented 2019年10月6日 14:40

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。