指定した合計値を作れる要素を出力するCプログラム

この記事では、ユーザーが入力した複数の要素の中から、指定した合計値を満たすことができる要素を順番に取り出して表示するCプログラムを紹介します。まず要素数Nと各要素の値を入力し、続いて確認したい合計値を入力します。プログラムは配列を先頭から順に走査しながら、合計値をオーバーしない範囲で要素を選んでいきます。

実行例

入力例：N=5
    5つの値を入力：3 1 6 5 7
    確認したい合計値：10
出力例：3 1 6

アルゴリズム

START
STEP1-> ユーザーから値を受け取る
STEP2-> 確認したい合計値を受け取る
STEP3-> i = 0; i < n; i++ の繰り返し処理を行う
STEP4-> もし sum - *(ptr+i) >= 0 であれば、
    STEP4.1-> sum -= *(ptr+i);
    STEP4.2-> *(ptr+i) の値を出力する
END If
END For
STOP

プログラムの仕組み

このプログラムは貪欲法（グリーディ法）に基づいています。入力された要素を先頭から順に調べ、「現在の残り合計値からその要素を差し引いても0以上になる」場合のみその要素を採用します。採用した分だけ合計値を減らしながら走査を続け、最終的に出力された要素の並びが「指定した合計を形成できる組み合わせ」になります。

サンプルコード

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char const *argv[]){
    int *ptr, n, i, sum;
    printf("Enter number of digits you want to enter\n");
    scanf("%d", &n);
    ptr = (int*)malloc(sizeof(int)*n); // int型のメモリを動的に確保
    printf("Enter %d elements\n", n);
    for(i = 0; i < n; i++) {
       scanf("%d", (ptr+i)); // 動的に確保した配列へ値を入力
    }
    printf("Enter the sum you want to check\n");
    scanf("%d", &sum);
    for (i = 0; i < n; i++) {
       if(sum - *(ptr+i) >= 0) { // 合計を構成できるかどうかを判定
          sum -= *(ptr+i); // 残りの合計値を更新
          printf("%d ", *(ptr+i)); // 合計を構成できる値を出力
       }
    }
    return 0;
}

ポイント解説

• 動的メモリ確保： mallocを使って、ユーザーが指定した個数分のint型領域を実行時に確保しています。mallocを使用するため、<stdlib.h>のインクルードが必要です。
• 条件判定： sum - *(ptr+i) >= 0という条件で、その要素を加えても合計値を超えないことを確認してから採用します。
• ポインタ操作： *(ptr+i)は配列のi番目の要素を表しており、ポインタ演算によって要素へアクセスしています。

出力結果

上記のプログラムを実行すると、次のような出力が得られます。

Enter number of digits you want to enter
5
Enter 5 elements
3
1
6
5
7
Enter the sum you want to check
10
3 1 6

この例では、合計値として10が指定されています。先頭から順に「3」「1」「6」を足すとちょうど10になるため、これら3つの要素が出力されました。なお、この手法はあくまで先頭から順に選ぶ貪欲なアプローチであるため、必ずしもすべての組み合わせや最適解を網羅するものではない点に注意してください。