10094. Fast 0/1 Knapsack Problem (OpenMP)

I'm a slow walker, but I never walk backwards.

題目描述

有 $N$ 個重量和價值分別為 $W_i, V_i$ 的物品,現在要從這些物品中選出總重量不超過 $M$ 的物品,求所有挑選方案中的總價值最大值為何。

輸入格式

輸入只有一組測資,第一行會有兩個整數 $N, M$ 分別表示物品數量和背包能容大的最大重量 $M$。接下來會有 $N$ 行,第 $i$ 行上會有兩個整數 $W_i, V_i$,分別為物品 $i$ 的重量和價值。

  • $1 \le N \le 10000$
  • $1 \le M \le 1000000$
  • $1 \le W_i, \; V_i \le 100000$

輸出格式

輸出一行整數,挑選方案中的最大價值 $B$。

範例輸入

4 5
2 3
1 2
3 4
2 2

範例輸出

7

編譯參數

gcc -std=c99 -O2 -fopenmp main.c -o main -lm
g++ -std=c++98 -O2 -fopenmp main.cpp -o main -lm

Discussion