C言語のプログラムができないので、Cのソースコードを教えてください！！

Question

私は今問題を解こうとして、C言語を使ったプログラミングを作ろうとしているのですが、どのように
実際のソースコードを作ればいいのかがわかりません。なので以下の問題をとくプログラムのソースコードを教えてください！！（なるべくかんたんなソースコードがいいです。）

問題

額面がそれぞれ3,6,11、28、57、86、119の紙幣がそれぞれ1枚ずつある。これらの紙幣を使ってちょうど（過不足なく）支払うことのできない金額を次から選び、小さい順に列挙せよ。
299 111 128 71 328 255 239 260 151 163 246 184 253 97 78 114

Comments

[y_waiwai]

無駄に質問を立てないように。
質問は編集できるので追記修正しましょう

[BeatStar]

丸投げやマルチポストは禁止ですよ。
https://teratail.com/help/avoid-asking

[meg_]

他の言語は出来るのですか？？

Answer 1

残念ながら、コード作成依頼は受けつけていません

Answer 2

7枚のお札しかないのなら、組み合わせは2^7=128 なんで、全通り求めてしまえばいいと思いますけどね
ちょっと面白いやり方が思いついたのでソース書いてみたテスト

#define MONEY 7

int money[1 << MONEY] = {0};

int bill[MONEY] = {3,6,11,28,57,86,119};

for (int i = 0; i < MONEY; i++){
	int width = (1 << i);
	for (int j = 0; j < width; j++){
		money[width + j] = money[j] + bill[i];
	}
}

Comments

[rubato6809]

この回し方はあまり使わないので、確かに面白いと思いました。
ただ、できた配列 money[] は、この後、どう使う予定なんでしょうか。さほど効率の良いデータ構造とは思えない、という疑問です。

[izmktr]

ソートしてバイナリサーチで当てればよくないです？(ついでに重複削除とか)
ワークメモリを使わず、計算量をO(n^2)とするよりはこっちのほうが面白いかなぁと
ワークメモリ無しでO(n)の方法があれば理想ですけどね

Answer 3

この問題は少なくとも２方向のアプローチがあり、面白いと思いました。中級以上の人向けかなと。この質問者のレベルで、なぜこんな問題を解かにゃならんの？

• 目的の金額をこれらの紙幣の組合わせで作れないか、バックトラック法で探す。

自然なアプローチに思えますが、再帰を使うので初心者向きかな？と疑問。

• 金額（1円〜500円程度）をインデックスにして、払える・払えないの配列を作る。それには予め7枚の紙幣で払える全ての組み合わせ金額を総当りで挙げれば良い。

一旦その配列を作ってしまえば、目的の金額が払える・払えないの判定は一瞬。

forループ一個で全ての組み合わせを総当り検査するという方法は、Ｃ言語でナップザック問題 総当たりで悩んでいますで使ったものです。
この時、再帰で調べる方法を示した方がいらっしゃいました。再帰ですから、私のバックトラック法に相当するようです。

ソートの手段もいろいろ選べます。私はqsort()を使う方法と、支払えないと判定した金額を、単方向リストの適切な位置に挿入することでソートしてしまう方法を試しました。コードは書けたので、そのプログラムの動作中の様子を表示して途中のデータの様子などを見てもらってイメージだけでも掴んでもらおうと思ったのですが、気づいたら既に質問者のアカウントが凍結されていたというお粗末（苦笑）。

---

izmktrさん

組み合わせは2^7=128 なんで、全通り求めてしまえばいい

それが私の試した方法のひとつなので、私もその一部をアップします。

金額（1円〜500円程度）をインデックスにして、払える・払えないの配列を作る…

#include <stdio.h>
#include <stdbool.h>
int target_prices[] = {
    299, 111, 128,  71, 328, 255, 239, 260,
    151, 163, 246, 184, 253,  97,  78, 114,
};
int bills[] = { 3, 6, 11, 28, 57, 86, 119 };
bool able2pay[500];     // 最初は全て支払い不能（0〜499円に対して）
#define N_BILLS   (sizeof(bills) / sizeof(bills[0]))
#define N_PRICES  (sizeof(target_prices) / sizeof(target_prices[0]))
int main(void)
{
    // 7枚の札、全ての組合せを調べ、支払い可能な金額は true
    printf("1. build the flag table.\n");
    for (int i = 1; i < (1 << N_BILLS); ++i) {
        int mask = 1, sum = 0;

        for (int j = 0; j < N_BILLS; ++j, mask += mask) {
            if (i & mask)
                sum += bills[j];  // この組み合わせに含まれる金額を足す
        }
        able2pay[sum] = true;     // 合計金額sum円は支払い可能
    }

    printf("2. prices unable to pay are\n");
    for (int i = 0; i < N_PRICES; ++i) {
        if (! able2pay[target_prices[i]])
            printf(" %d", target_prices[i]);
    }
	printf("\n");

    printf("TODO: sort above.\n");
    return 0;
}