東京工業大学 情報理工学院 情報工学系 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$ と並べ、$1\le i<i'\le N$ ならば $\operatorname{volume}(g_i)\le\operatorname{volume}(g_{i'})$ とする。$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}$$

漸化式は $1\le i\le N,\ j\ge1$ に対するもので、$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

表3.2には $T_{i,j}$ の値が次のように与えられている。

$T_{i,j}$	$W_0$	$W_1$	$W_2$	$W_3$	$W_4$	$W_5$	$W_6$	$W_7$	$W_8$
$G_0$	0	①	①	①	①	①	①	①	①
$G_1$	②	5	5	5	5	5	5	5	5
$G_2$	②	5	6	6	11	11	11	11	11
$G_3$	②	5	6	7	11	③	④	⑤	⑥
$G_4$	②	5	6	7	11

(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).$$

部分項にも規則を適用でき、すなわち $x\Rightarrow x'$ なら $xy\Rightarrow x'y$、$y\Rightarrow y'$ なら $xy\Rightarrow xy'$ である。適用できなくなった項を正規形と呼ぶ。リダクションの例は次のとおりである。

$$SIIx\Rightarrow Ix(Ix)\Rightarrow x(Ix)\Rightarrow xx,$$

$$\begin{aligned} S(K(SI))Kxy &\Rightarrow K(SI)x(Kx)y\Rightarrow SI(Kx)y\\ &\Rightarrow Iy(Kxy)\Rightarrow y(Kxy)\Rightarrow yx. \end{aligned}$$

(a) 任意の項 $x$ について、$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)$$

と定義する。このとき、任意の項 $x,y$ に対して次の変換が成り立つ。

$$\begin{aligned} \lor xy&=SI(KT)xy\Rightarrow Ix(KTx)y\Rightarrow x(KTx)y\Rightarrow xTy,\\ \land xy&=SS(K(KF))xy\Rightarrow Sx(K(KF)x)y\Rightarrow xy(K(KF)xy)\Rightarrow xy(KFy)\Rightarrow xyF,\\ \neg x&=S(SI(KF))(KT)x\Rightarrow SI(KF)x(KTx)\\ &\Rightarrow Ix(KFx)(KTx)\Rightarrow x(KFx)(KTx)\Rightarrow xF(KTx)\Rightarrow xFT. \end{aligned}$$

これらを用い、(iii) $\lor(\neg T)T$、(iv) $\lor(\neg T)F$、(v) $\land(\neg F)T$、(vi) $\land(\neg F)F$ を正規形にし、過程も示せ。

题目描述

用按可达体积压缩的动态规划求0–1背包表及最优组合；各物品按体积非递减排列，已知表项和编号空格见表 3.2。根据 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$ はいずれも引数不足なので、それ以上規則を適用できない正規形である。