有 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]);