물건 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
무게당 가치가 큰 것부터 담는 욕심(greedy)은 틀려요: 예시 1에서 무게당 가치가 가장 큰 5짜리(12)를 먼저 넣으면 남은 2에 아무것도 못 넣어서 12지만, 답은 4 + 3으로 14예요.
그래서 동적 계획법(DP)을 써요.best[c] = 무게 합 c 이하로 얻는 가장 큰 가치로 두고, 물건마다 best[c] = max(best[c], best[c - w] + v)로 고쳐요.
표를 n × W 2차원으로 만들 필요는 없어요: 한 줄(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으로 시작하고 스택도 쓰지 않아요), 크레이콘 새목록(W + 1, 0) — 크레이콘 목록은 10,000칸까지라 W를 9,999까지로 두었어요.
거꾸로 도는 반복: Python range(W, w - 1, -1)(끝 w - 1은 들어가지 않아요), C 계열·크레이콘 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]);