問題: ナップサック問題 (C)

ナップサック問題 (C)

問題

品物の数 n とナップサックの容量を入力し、続けて各品物の重さと価値を受け取って、容量を超えない範囲で詰められる価値の最大値を求めてください。動的計画法を用い、dp[w] に重さの合計が w 以下のときの価値の最大値を記録します。同じ品物を二回使わないよう、w は大きい方から更新します。

入力例

出力例

価値の最大値: 7

残り時間: 00:00

速度: 0 文字/分

参照コード

コピーはできません。自分でタイピングしてください。

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main(int argc, const char *argv[]) {
    int n, capacity;
    int weight[100], value[100];
    int dp[1001] = {0};
    scanf("%d %d", &n, &capacity);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }

    printf("価値の最大値: %d\n", dp[capacity]);
    return 0;
}

ナップサック問題 (C)

問題

入力例

出力例

参照コード

入力エリア