重さの上限までに積む荷物の価値の最大

動的計画法
問題 17
やや難しい
目安 45 分

配送の車に、重さの上限を越えないように荷物を選んで積むとき、価値の合計の最大を求める。重さごとの最大の価値を表に残す、動的計画法の練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

配送の車に、N 個の荷物の中からいくつかを選んで積みます。i 個目の荷物は重さが w_i、価値が v_i です。車に積める重さの合計は W までです。

それぞれの荷物は、積むか積まないかのどちらかで、同じ荷物を 2 回積むことはできません。積んだ荷物の重さの合計が W 以下になるように選ぶとき、価値の合計の最大を出力してください。1 つも積まないときの価値の合計は 0 です。

入力の形式

N W
w_1 v_1
w_2 v_2
...
w_N v_N

1 行目に荷物の数 N と重さの上限 W が半角の空白 1 つで区切られて並びます。続く N 行は、1 行に 1 つの荷物の重さ w_i と価値 v_i です。

出力の形式

価値の合計の最大を 1 行で出力します。

制約

N は 1 以上 100 以下の整数です
W は 1 以上 10000 以下の整数です
w_i は 1 以上 10000 以下の整数です (W より重い荷物もあります)
v_i は 1 以上 2000000 以下の整数です

入力と出力の例

例 1

上限が 5 で、荷物が 4 個あります。重さ 2 で価値 3 の荷物と、重さ 3 で価値 4 の荷物を積むと、重さ 5 で価値 7 になります。これより大きい価値の積み方はありません。

入力

出力

例 2

上限が 3 で、どの荷物も 3 より重いので、1 つも積めません。答えは 0 です。

入力

2 3
4 10
5 20

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

best[c] を「重さの合計を c 以下にしたときの、価値の合計の最大」として、0 で始めます。荷物を 1 つずつ見て、c を W から荷物の重さまで大きい順に回し、best[c - 重さ] + 価値が best[c] より大きければ書き換えます。大きい順に回すので、best[c - 重さ] はまだ今の荷物を積んでいない値で、同じ荷物を 2 回積むことはありません。全部の荷物を見たあとの best[W] が答えです。荷物 N 個のそれぞれで表を 1 回書き換えるので、全部で O(N × W) です。

Python

import sys

data = sys.stdin.read().split()
n, w = int(data[0]), int(data[1])
items = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)]

best = [0] * (w + 1)
for weight, value in items:
    for cap in range(w, weight - 1, -1):
        if best[cap - weight] + value > best[cap]:
            best[cap] = best[cap - weight] + value

print(best[w])

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const w = data[1];

const best = new Array(w + 1).fill(0);
for (let i = 0; i < n; i++) {
  const weight = data[2 + 2 * i];
  const value = data[3 + 2 * i];
  for (let cap = w; cap >= weight; cap--) {
    if (best[cap - weight] + value > best[cap]) best[cap] = best[cap - weight] + value;
  }
}

console.log(best[w]);

計算量

時間は O(N × W)、メモリは O(W) です。N が 100、W が 10000 なら、100 万回ほどの計算で済みます。

遅い解き方は、荷物ごとに積むか積まないかを全部試すものです。2^N 通りあるので、N が 15 なら 3 万通りほどで終わりますが、N が 100 では 2^100 通りで終わりません。途中で重さが上限を越えた時点で打ち切っても、軽い荷物が多いと選び方の数は減らず、やはり終わりません。

よくある間違い

1 つの表を使い回すのに、c を小さい順に回す。同じ荷物を何回も積んだ値になり、答えが大きすぎます
重さあたりの価値が高い順に積む貪欲法で答える。ヒント 1 の例のように外れます
W より重い荷物で best[c - 重さ] を読み、Python では負の番号が表の後ろを指して、間違った値を使ってしまう。c の範囲を荷物の重さ以上に限ります
2 次元の表 (荷物の数 × 重さ) を作り、前の行を写すのを忘れて、積まない場合の値が 0 になる

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n, w = int(data[0]), int(data[1])
items = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)]

# ここから書く

入力

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します