京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F2-2

标签：

• Kyoto-University
• Knapsack-Problem
• Zero-One-Knapsack-Recurrence
• Greedy-Failure-for-Zero-One-Knapsack

Author

Isidore, 祭音Myyura

Description

ナップサック問題の入力は、非負整数の容量 $c$ を持つナップサックと、$n$ 個のアイテム $a_1, a_2, \ldots, a_n$ からなる。 各アイテム $a_i$ は正整数の重さ $w_i \ (\leq c)$ と 正整数の価値 $p_i$ を持つ。 アイテムの集合 $S$ の合計重さと合計価値は、それぞれ $S$ に含まれるアイテムの重さの総和、価値の総和と定義する。 ナップサックには、合計重さ $c$ 以下のアイテム集合を詰め込むことができる。 ナップサックに詰め込むことのできるアイテム集合のうち合計価値が最大となるものをその入力に対する最適解、最適解の合計価値をその入力に対する最適値と呼ぶ。

$n=6, c=10$ で、アイテムが以下の表で与えられる入力を $I$ とする。

アイテム	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$
重さ $w_i$	2	3	3	4	4	5
価値 $p_i$	3	4	5	6	7	8

設問1 入力 $I$ に対する最適値と 、全ての最適解を答えよ。

設問2 アイテムを単位重さ当たりの価値が大きい順に「ナップサックに入れることができれば入れ、できなければ捨てる」という逐次処理をし、最後にナップサックに入っているアイテム集合を出力するアルゴリズムを考える。 ただし、単位重さ当たりの価値が同じアイテムが複数あれば、価値の高いものを先に処理する。 入力 $I$ にこのアルゴリズムを適用させた場合の出力を答えよ。

設問3 $n \leq 4, c = 10$ で、設問2のアルゴリズムが出力するアイテム集合の合計価値が最適値の $5$ 倍以上悪く（小さく）なる入力例を1つ示せ。 また、最適解とアルゴリズムの出力を示すことにより、その答えが設問の要件を満たしていることを説明せよ。

設問4 $1 \leq i \leq n, 0 \leq j \leq c$ を満たす整数 $i,j$ に対し、アイテムが $a_1, \ldots, a_i$ でナップサック容量が $j$ である部分問題の最適値を $\text{OPT}(i,j)$ とする。 上記の入力 $I$ に対して $\text{OPT}(1,1), \text{OPT}(2,4), \text{OPT}(3,5)$ の値を答えよ。

設問5 設問4で定義した $\text{OPT}(i,j)$ を $i$ や $j$ の値が小さいものから順に計算していくアルゴリズムを考える。 以下の問いに答えよ。なお本設問は、上記の具体的な入力 $I$ に対して ではなく一般の入力に対する問いであるので注意すること。

• (1) $\text{OPT}(i, 0)$ の値を答えよ。
• (2) $\text{OPT}(1,j)$ の値を答えよ。
• (3) $i \geq 2, j \geq 1$ とし、$1 \leq a \leq i-1, 0 \leq b \leq j$ および $a = i, 0 \leq b \leq j-1$ を満たす全ての $a,b$ について $\text{OPT}(a,b)$ が求まっているとする。 このとき $\text{OPT}(i,j)$ を求める計算方法を答えよ。

Kai

設問1

The optimal value is $16$, while there is 3 solutions

$$\{a_5, a_3, a_2\} , \{a_5, a_4, a_1\}, \{a_1, a_3, a_6\}$$

設問2

アイテム	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$
$p_i/w_i$	$1.50$	$1.33$	$1.67$	$1.50$	$1.75$	$1.60$

The output value is $15$, while the output solution is

$$\{a_5, a_3, a_1\}$$

設問3

Design the input like below

	$a_1$	$a_2$
w	1	10
p	2	10
p/w	2	1

Obviously, by comparing the value per weight, performing the algorithm defined in Q.2 will results in the output

$$2,\{a_1\}$$

However, the actual optimal value with solution is

$$10, \{a_2\}$$

which is 5 times better than the former.

設問4

$$\begin{aligned} \text{OPT}(1,1) = 0 \\ \text{OPT}(2,4) = 4 \\ \text{OPT}(3,5) = 8 \\ \end{aligned}$$

設問5

(1)

$$\text{OPT}(i,0) = 0$$

(2)

$$\text{OPT}(1, j) = \begin{cases} p_{1}&(j\geq w_{1})\\ 0&(j<w_{1}) \end{cases}$$

(3)

$$\text{OPT}(i,j) = \begin{cases} \max(\text{OPT}(i-1,j), \text{OPT}(i-1,j-w_{i})+p_{i})&(j\geq w_{i})\\ \text{OPT}(i-1,j)&(j<w_{i}) \end{cases}$$