現在のご質問文中で「回文の中に回文といった構造」と言うのは、
こんな構造↓
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を学習した人にチェックされるとダメ出しを食らうような部分があるかもしれません。)
ただし、プログラミングチャレンジの出題のような場合、「単純な総当たり」では時間切れになってしまうような設定になっていることが多いです。上記のように「組み合わせ」だけを別途求めるようにすると、単純な枝刈りさえ難しくなるので、あまりお勧めはしにくい解き方ということになります。
//
を使いましょう。/*
を使われていますが、閉じるための*/
が抜けています。 / 「n個の商品」は個数でなく「種類」ならcnt
と紛らわしくなるので注意した方がよさそうです。cnt
も入力として与えられる問題を解こうとしていて、今思いついている解き方だとcnt
が固定であればその数だけfor
をネストさせれば解けるのだけど、cnt
が任意に与えられた場合の解き方が分からない、ということでしょうか?