品物が n 個と、重さの合計 W まで入るナップサックが一つある。
i 番目の品物の重さは wᵢ、価値は vᵢ である。
品物ごとに、ナップサックに入れるか入れないかのどちらかだけを選べる。
一つの品物を二回入れたり、分けて入れたりはできない。
入れた品物の重さの合計が W 以下になるように選ぶとき、入れた品物の価値の合計として可能な最大の値を出力せよ。
どの品物も入れられなければ 0 を出力する。
4 7 6 13 4 8 3 6 5 12
14
2 5 6 100 7 50
0
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
重さあたりの価値が大きいものから詰める貪欲法は間違いです：例 1 では重さあたりの価値が最も大きい重さ 5 の品物（12）を先に入れると残り 2 に何も入らず 12 ですが、答えは 4 + 3 で 14 です。
そこで動的計画法（DP）を使います。best[c] = 重さの合計 c 以下で得られる最大の価値とし、品物ごとに best[c] = max(best[c], best[c - w] + v) で更新します。
n × W の二次元の表は要りません：一行（W + 1 マス）を持ち、c を大きい方から小さい方へ回せば best[c - w] はまだこの品物を入れる前の値です。
小さい方から回すと、たった今この品物を入れた値をまた読んで、一つの品物を何回も入れてしまいます（それは個数制限のないナップサックです）— いちばん多い罠です。
重さが W より大きい品物はループが一度も回らないので自然に外れます。
価値の合計は最大 1 億なので、どの言語でも 32 ビット整数に収まります。
一行の作り方：Python [0] * (W + 1)、JavaScript・TypeScript new Array(W + 1).fill(0)、Java new int[W + 1]・C# new int[W + 1]（0 で埋まっています）、C++ std::vector<int>(W + 1, 0)、C は static int best[10000]（static なので 0 から始まり、スタックも使いません）、Craykon 新リスト(W + 1, 0) — Craykon のリストは 10,000 個までなので W を 9,999 までにしました。
逆向きのループ：Python range(W, w - 1, -1)（終わりの w - 1 は含まれません）、C 系・Craykon c = W; c >= w; c--。
n, W = map(int, input().split()) # best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서)best = [0] * (W + 1)for _ in range(n): w, v = map(int, input().split()) # 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for c in range(W, w - 1, -1): if best[c - w] + v > best[c]: best[c] = best[c - w] + vprint(best[W])const [n, W, ...rest] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서)const best = new Array(W + 1).fill(0);for (let i = 0; i < n; i++) { const w = rest[2 * i], v = rest[2 * i + 1]; // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for (let c = W; c >= w; c--) { best[c] = Math.max(best[c], best[c - w] + v); }}console.log(best[W]);import { readFileSync } from "node:fs"; const [n, W, ...rest]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서)const best: number[] = new Array<number>(W + 1).fill(0);for (let i = 0; i < n; i++) { const w: number = rest[2 * i], v: number = rest[2 * i + 1]; // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for (let c = W; c >= w; c--) { best[c] = Math.max(best[c], best[c - w] + v); }}console.log(best[W]);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int W = Integer.parseInt(st.nextToken()); // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서) int[] best = new int[W + 1]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); int w = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for (int c = W; c >= w; c--) { best[c] = Math.max(best[c], best[c - w] + v); } } System.out.println(best[W]); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int W = int.Parse(first[1]); // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서) int[] best = new int[W + 1]; for (int i = 0; i < n; i++) { string[] item = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int w = int.Parse(item[0]); int v = int.Parse(item[1]); // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for (int c = W; c >= w; c--) { best[c] = Math.Max(best[c], best[c - w] + v); } } Console.WriteLine(best[W]); }}#include <algorithm>#include <iostream>#include <vector> int main() { int n, W; std::cin >> n >> W; // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서) std::vector<int> best(W + 1, 0); for (int i = 0; i < n; i++) { int w, v; std::cin >> w >> v; // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 for (int c = W; c >= w; c--) { best[c] = std::max(best[c], best[c - w] + v); } } std::cout << best[W] << "\n";}#include <stdio.h> int main(void) { int n, W; scanf("%d %d", &n, &W); /* best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서) */ static int best[10000]; /* static이라 0으로 채워져 있다 */ for (int i = 0; i < n; i++) { int w, v; scanf("%d %d", &w, &v); /* 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 */ for (int c = W; c >= w; c--) { if (best[c - w] + v > best[c]) best[c] = best[c - w] + v; } } printf("%d\n", best[W]); return 0;}첫줄 = コンソール.数読み();n = 첫줄[0];W = 첫줄[1]; // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서)// 목록 하나에 10,000칸까지라 W + 1칸짜리 한 줄만 쓴다best = 新リスト(W + 1, 0);繰り返す (i = 0; i < n; i++){ 물건 = コンソール.数読み(); w = 물건[0]; v = 물건[1]; // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다 繰り返す (c = W; c >= w; c--) { best[c] = 数学.大きい方(best[c], best[c - w] + v); }}コンソール.書く(best[W]);