東京工業大学 情報理工学院 情報工学系 2018年8月実施 午前 3.

标签：

• institute-of-science-tokyo
• Knapsack-Problem
• Programming

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

1)

品物を体積の昇順に $g_1,\ldots,g_N$ と並べ、$G_0=\varnothing$、$G_i=G_{i-1}\cup\{g_i\}$ とする。全品物の部分集合が取り得る体積合計を重複を除き昇順に $W_0,W_1,\ldots$ と並べる（$W_0=0$）。$G_i$ から容量 $W_j$ 以下で選べる最大価値を $T_{i,j}$ とする。

$$T_{0,0}=0,\qquad T_{0,j}=\boxed{1}\ (j\ge1),\qquad T_{i,0}=\boxed{2},$$

$$T_{i,j}=\begin{cases}T_{i-1,j}&W_j<\operatorname{volume}(g_i),\\ \max\{T_{i-1,j},T_{i-1,h}+\operatorname{value}(g_i)\}&W_j\ge\operatorname{volume}(g_i),\end{cases}$$

ただし $h=\max\{k:W_k\le W_j-\operatorname{volume}(g_i)\}$。

品物	体積	価値
$g_1$	10	5
$g_2$	15	6
$g_3$	20	7
$g_4$	30	8

(a) $G_1,\ldots,G_4$ を列挙せよ。(b) $W_0,\ldots,W_8$ を求めよ。 (c) ①、②および $T_{3,5}=\boxed{3},T_{3,6}=\boxed{4},T_{3,7}=\boxed{5},T_{3,8}=\boxed{6}$ を求めよ。 (d) 容量 $W_5,W_6,W_7,W_8$ に対する全品物 $G_4$ の最適な組合せと価値を求めよ。

2)

項は定数 $S,K,I$ と二項適用から作り、適用は左結合とする。計算規則は

$$Ix\Rightarrow x,\qquad Kxy\Rightarrow x,\qquad Sxyz\Rightarrow xz(yz).$$

部分項にも規則を適用でき、適用できなくなった項を正規形と呼ぶ。 (a) $SKKx$ と $Ix$ のリダクション結果が同じになることを示せ。 (b) $T=K,F=KI$ とする。正規形の項 $x,y$ に対し (i) $Txy$、(ii) $Fxy$ を正規形まで変換せよ。 (c)

$$\lor=SI(KT),\quad \land=SS(K(KF)),\quad\neg=S(SI(KF))(KT)$$

と定義する。このとき $\lor xy\Rightarrow^*xTy$、$\land xy\Rightarrow^*xyF$、$\neg x\Rightarrow^*xFT$ を用い、(iii) $\lor(\neg T)T$、(iv) $\lor(\neg T)F$、(v) $\land(\neg F)T$、(vi) $\land(\neg F)F$ を正規形にし、過程も示せ。

题目描述

用按可达体积压缩的动态规划求0–1背包表及最优组合；根据 SKI 组合子的归约规则，化简恒等组合子和以组合子编码的布尔运算。

Kai

1)

a)

$$G_1=\{g_1\},\quad G_2=\{g_1,g_2\},\quad G_3=\{g_1,g_2,g_3\},\quad G_4=\{g_1,g_2,g_3,g_4\}.$$

b)

$$\boxed{(W_0,\ldots,W_8)=(0,10,15,20,25,30,35,40,45)}.$$

c)

$$(1)=0,\quad(2)=0,\quad(3)=12,\quad(4)=13,\quad(5)=13,\quad(6)=18.$$

例えば容量30では $g_1,g_3$ の価値12、容量35,40では $g_2,g_3$ の価値13、容量45では $g_1,g_2,g_3$ の価値18が最適である。

d)

容量	最適な組合せ	体積合計	価値合計
$W_5=30$	$\{g_1,g_3\}$	30	12
$W_6=35$	$\{g_2,g_3\}$	35	13
$W_7=40$	$\{g_2,g_3\}$ または $\{g_1,g_4\}$	35 または 40	13
$W_8=45$	$\{g_1,g_2,g_3\}$	45	18

2)

a)

$$SKKx\Rightarrow Kx(Kx)\Rightarrow x,\qquad Ix\Rightarrow x.$$

従って両者は同じ項 $x$ に帰着する。

b)

$$\text{(i)}\quad Txy=Kxy\Rightarrow x,$$

$$\text{(ii)}\quad Fxy=KIxy\Rightarrow Iy\Rightarrow y.$$

$x,y$ は正規形なのでここで終了する。

c)

まず

$$\neg T\Rightarrow^*TFT=KFT\Rightarrow F=KI,$$

$$\neg F\Rightarrow^*FFT=KIFT\Rightarrow IT\Rightarrow T=K.$$

問題で示された変換を用いると

$$\begin{aligned} \text{(iii)}\quad\lor(\neg T)T&\Rightarrow^*\lor FT\Rightarrow^*FTT=KITT\Rightarrow IT\Rightarrow T=\boxed K,\\ \text{(iv)}\quad\lor(\neg T)F&\Rightarrow^*\lor FF\Rightarrow^*FTF=KITF\Rightarrow IF\Rightarrow F=\boxed{KI},\\ \text{(v)}\quad\land(\neg F)T&\Rightarrow^*\land TT\Rightarrow^*TTF=KTF\Rightarrow T=\boxed K,\\ \text{(vi)}\quad\land(\neg F)F&\Rightarrow^*\land TF\Rightarrow^*TFF=KFF\Rightarrow F=\boxed{KI}. \end{aligned}$$

$K$ と $KI$ はいずれも引数不足なので、それ以上規則を適用できない正規形である。