GLPK/揹包問題

揹包問題是 揹包問題，來自 組合最佳化 的一個經典裝箱問題。

揹包問題可以定義如下：給定一組大小為 $N$ 的物品 $s_{i}$ 和利潤 $p_{i}$，選擇一個子集，這些子集適合容量 $c$ 並且最大化所選物品的總利潤。

最大化	$\sum _{N}p_{i}x_{i}\quad x_{i}\in \{0,1\}$
受制於	$\sum _{N}s_{i}x_{i}\leq c$

揹包問題屬於 NP-hard 問題類 。

解決揹包問題的一種常用方法是透過 動態規劃 (DP)。下面的示例展示瞭如何將揹包問題公式化為在 GMPL (MathProg) 中實現的混合整數規劃 (MIP)。

# en.wikipedia.org offers the following definition:
# The knapsack problem or rucksack problem is a problem in combinatorial optimization:
# Given a set of items, each with a weight and a value, determine the number of each
# item to include in a collection so that the total weight is less than a given limit
# and the total value is as large as possible.
#
# This file shows how to model a knapsack problem in GMPL.

# Size of knapsack
param c;

# Items: index, size, profit
set I, dimen 3;

# Indices
set J := setof{(i,s,p) in I} i;

# Assignment
var a{J}, binary;

maximize obj :
  sum{(i,s,p) in I} p*a[i];

s.t. size :
  sum{(i,s,p) in I} s*a[i] <= c;

solve;

printf "The knapsack contains:\n";
printf {(i,s,p) in I: a[i] == 1} " %i", i;
printf "\n";

data;

# Size of the knapsack
param c := 100;

# Items: index, size, profit
set I :=
  1 10 10
  2 10 10
  3 15 15
  4 20 20
  5 20 20
  6 24 24
  7 24 24
  8 50 50;

end;

現在使用 GLPSOL 儲存並執行此模型（在 Intel Core i5 處理器上花費 1 秒）。

$ glpsol --math knapsack.mod

得到

The knapsack contains:
 2 4 5 8