dynamic programmingP0116

Packing a knapsack

There are n items and one knapsack that holds a total weight of up to W. Item i has weight wᵢ and value vᵢ. For each item you either put it in the knapsack or leave it out. An item cannot be put in twice or cut into pieces. Choosing items so that their total weight is at most W, print the largest possible total value of the chosen items. If no item can be put in, print 0.

Input: The first line has n and W; each of the next n lines has wᵢ and vᵢ separated by a space.
1 ≤ n ≤ 100, 1 ≤ W ≤ 9,999, 1 ≤ wᵢ ≤ 10,000, 1 ≤ vᵢ ≤ 1,000,000
Output: One number: the largest total value

Example 1 · stdin

stdout

Example 2 · stdin

2 5
6 100
7 50

stdout

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Greedily taking the best value per weight first is wrong: in example 1 the weight-5 item (12) has the best ratio, but after it nothing fits in the remaining 2, giving 12, while the answer is 4 + 3 for 14.
So use dynamic programming (DP).
Let best[c] be the largest value with total weight at most c, and for each item update best[c] = max(best[c], best[c - w] + v).
You do not need an n × W 2D table: keep one row (W + 1 cells) and loop c from large to small, so best[c - w] is still the value from before this item.
Looping from small to large reads a value that already includes this item and puts one item in many times (that is the unlimited-copies knapsack) — the most common trap.
Items heavier than W drop out by themselves because the loop never runs.
The total value is at most 100 million, so it fits a 32-bit int in every language.
Making the row: Python [0] * (W + 1), JavaScript/TypeScript new Array(W + 1).fill(0), Java new int[W + 1] and C# new int[W + 1] (already zero), C++ std::vector<int>(W + 1, 0), C static int best[10000] (static starts at zero and does not use the stack), Craykon NewList(W + 1, 0) — Craykon lists hold up to 10,000 items, which is why W goes only up to 9,999.
The backward loop: Python range(W, w - 1, -1) (the end w - 1 is excluded), the C family and Craykon c = W; c >= w; c--.

Pythonmain.py · 11 lines

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

JavaScriptmain.js · 12 lines

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

TypeScriptmain.ts · 14 lines

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

JavaMain.java · 26 lines

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

C#Main.cs · 26 lines

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

C++main.cpp · 20 lines

#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";}

Cmain.c · 19 lines

#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;}

Craykonmain.cray · 19 lines

첫줄 = Console.ReadNumbers();n = 첫줄[0];W = 첫줄[1]; // best[c] = 무게 합이 c 이하일 때 얻는 가장 큰 가치(지금까지 본 물건만 써서)// 목록 하나에 10,000칸까지라 W + 1칸짜리 한 줄만 쓴다best = NewList(W + 1, 0);for (i = 0; i < n; i++){    물건 = Console.ReadNumbers();    w = 물건[0];    v = 물건[1];    // 큰 무게부터 거꾸로: best[c - w]가 아직 '이 물건을 넣기 전' 값이라 한 번만 넣는다    for (c = W; c >= w; c--)    {        best[c] = Mathf.Max(best[c], best[c - w] + v);    }}Console.WriteLine(best[W]);