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

标签：

• 东京科学大学
• 背包问题
• 组合子逻辑

Author

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

Description

1)

$N$ 個の品物の集合を $G$ とし，品物 $g\in G$ の体積を $\operatorname{volume}(g)$，価値を $\operatorname{value}(g)$ とする。$G$ の要素を体積の小さい順に並べた列を $(g_1,g_2,\ldots,g_N)$，つまり $1\le i<i'\le N$ のとき $\operatorname{volume}(g_i)\le\operatorname{volume}(g_{i'})$ とする。ここで容積 $W$ のナップザックが与えられたとき，$W$ の範囲内で価値の総和が最大となる品物の集合 $S\subseteq G$ を見つけることを考える。以下，$S$ を $G$ と $W$ に対するナップザック問題解と呼ぶ。

$G_0$ を空集合 $\varnothing$ とし，$1\le i\le N$ であるような $i$ について $G_i=G_{i-1}\cup\{g_i\}$ とする。次に0個以上の品物の体積の合計となり得る値の集合

$$\left\{\sum_{g\in X}\operatorname{volume}(g)\mathrel{\big|}X\subseteq G\right\}$$

の要素の値を小さい順に並べた列を $W_0,W_1,\ldots,W_j,\ldots$ とする。ただし $W_0$ は品物が0個の時の合計体積をあらわす。

このとき，品物の集合 $G_i$ と容積 $W_j$ のナップザックに対するナップザック問題解 $S_{i,j}$ の価値の総和 $T_{i,j}$ は下記の式で与えられる：ただし $\max U$ は実数の有限集合 $U$ の最大値を返す。

$$\begin{aligned} T_{0,0}&=0,\\ T_{0,j}&=\text{①}\qquad(\text{ただし }1\le j),\\ T_{i,0}&=\text{②},\\ T_{i,j}&=\begin{cases} T_{i-1,j}&(W_j<\operatorname{volume}(g_i)\text{ かつ }1\le j),\\ \begin{gathered}\max\{T_{i-1,j},\\T_{i-1,h}+\operatorname{value}(g_i)\}\end{gathered}&(W_j\ge\operatorname{volume}(g_i)\text{ かつ }1\le j). \end{cases} \end{aligned}$$

ただし

$$h=\max\{k\mid W_k\le(W_j-\operatorname{volume}(g_i))\}.$$

具体的に $G=\{g_1,g_2,g_3,g_4\}$ とし，それぞれの品物の体積と価値を表3.1で与える。この $G$ における $G_i$ と $W_j$ に対するナップザック問題解 $S_{i,j}$ を計算するための $T_{i,j}$ の値の表を表3.2に示す。この表の $i$ 行 $j$ 列に $T_{i,j}$ の値を入れる。

表3.1：各品物の体積と価値

品物	volume	value
$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,G_2,G_3,G_4$ の要素をそれぞれ列挙せよ。

b) $W_j\ (j=0,\ldots,8)$ の各値を示せ。

c) 表3.2の①～⑥の中に当てはまる値を記せ。

d) $G_4$ と $W_5,W_6,W_7,W_8$ に対するナップザック問題解 $S_{4,5},S_{4,6},S_{4,7},S_{4,8}$ の品物の組み合わせと価値の合計をそれぞれ求めよ。

2)

言語 $\omega$ の項を以下のように帰納的に定義する。

• 定数記号 $S,K,I$ は $\omega$ の項である。
• $x,y$ が $\omega$ の項のとき，$(x\cdot y)$ は $\omega$ の項である。
• 以上のようにして定義されるもののみが $\omega$ の項である。

この演算子 $\cdot$ は左結合的であり，記述を簡潔にするために演算子 $\cdot$ は省略できるものとする。すなわち $x,y,z\in\omega$ のとき $((x\cdot y)\cdot z)$ は $xyz$，$(x\cdot(y\cdot z))$ は $x(yz)$ と書くことができる。

次に $x,y,z\in\omega$ に対して，$S,K,I$ それぞれの計算規則（左辺から右辺への変換規則）を以下のように定義する。

$$\begin{aligned} Ix&\Rightarrow x,\\ Kxy&\Rightarrow x,\\ Sxyz&\Rightarrow xz(yz),\\ x\Rightarrow x'\quad&\text{ならば}\quad xy\Rightarrow x'y,\\ y\Rightarrow y'\quad&\text{ならば}\quad xy\Rightarrow xy'. \end{aligned}$$

上記の計算規則を用いて $\omega$ の項を変換することをリダクションと呼ぶ。リダクションはそれ以上変換できないとき停止するものとする。これ以上リダクションできない項は正規形と呼ばれる。リダクションの例を以下に示す。

$$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\in\omega$ について $SKKx$ と $Ix$ のリダクションの結果が同じとなることを示せ。

b) $T,F$ を以下のように定義する。

$$T=K,\qquad F=KI$$

このとき，以下の式 (i)(ii) を正規形までリダクションせよ。ただし，$x,y$ は正規形とする。また，リダクション結果とともに正規形を求めた過程を示すこと。

(i) $Txy$

(ii) $Fxy$

c) さらに $\lor,\land,\neg$ を以下のように定義する。

$$\begin{aligned} \lor&=SI(KT),\\ \land&=SS(K(KF)),\\ \neg&=S(SI(KF))(KT). \end{aligned}$$

これより，任意の $x,y\in\omega$ に対して，

$$\begin{aligned} \lor xy&=SI(KT)xy\Rightarrow Ix(KTx)y\\ &\Rightarrow x(KTx)y\Rightarrow xTy,\\[4pt] \land xy&=SS(K(KF))xy\Rightarrow Sx(K(KF)x)y\\ &\Rightarrow xy(K(KF)xy)\Rightarrow xy(KFy)\Rightarrow xyF,\\[4pt] \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)(iv)(v)(vi) を正規形までリダクションせよ。また，リダクション結果とともに正規形を求めた過程を示すこと。

(iii) $\lor(\neg T)T$

(iv) $\lor(\neg T)F$

(v) $\land(\neg F)T$

(vi) $\land(\neg F)F$

题目描述

1)

设 $N$ 个物品构成的集合为 $G$，物品 $g\in G$ 的体积为 $\operatorname{volume}(g)$，价值为 $\operatorname{value}(g)$。将 $G$ 的元素按体积从小到大排列成序列 $(g_1,g_2,\ldots,g_N)$，即当 $1\le i<i'\le N$ 时，$\operatorname{volume}(g_i)\le\operatorname{volume}(g_{i'})$。给定容积为 $W$ 的背包，考虑寻找在容积 $W$ 的范围内价值总和最大的物品集合 $S\subseteq G$。以下将 $S$ 称为关于 $G$ 和 $W$ 的背包问题解。

设 $G_0$ 为空集 $\varnothing$，对满足 $1\le i\le N$ 的 $i$，令 $G_i=G_{i-1}\cup\{g_i\}$。将0个或更多物品的总体积可能取到的值构成的集合

$$\left\{\sum_{g\in X}\operatorname{volume}(g)\mathrel{\big|}X\subseteq G\right\}$$

中的元素按从小到大排列成序列 $W_0,W_1,\ldots,W_j,\ldots$。其中 $W_0$ 表示物品数为0时的总体积。

对于物品集合 $G_i$ 和容积为 $W_j$ 的背包，其背包问题解 $S_{i,j}$ 的价值总和 $T_{i,j}$ 由下式给出。其中 $\max U$ 返回实数的有限集合 $U$ 的最大值。

$$\begin{aligned} T_{0,0}&=0,\\ T_{0,j}&=\text{①}\qquad(1\le j),\\ T_{i,0}&=\text{②},\\ T_{i,j}&=\begin{cases} T_{i-1,j}&(W_j<\operatorname{volume}(g_i)\text{ 且 }1\le j),\\ \begin{gathered}\max\{T_{i-1,j},\\T_{i-1,h}+\operatorname{value}(g_i)\}\end{gathered}&(W_j\ge\operatorname{volume}(g_i)\text{ 且 }1\le j). \end{cases} \end{aligned}$$

其中

$$h=\max\{k\mid W_k\le(W_j-\operatorname{volume}(g_i))\}.$$

具体设 $G=\{g_1,g_2,g_3,g_4\}$，各物品的体积和价值由表3.1给出。为了计算此 $G$ 中关于 $G_i$ 和 $W_j$ 的背包问题解 $S_{i,j}$，表3.2给出 $T_{i,j}$ 的值。在该表第 $i$ 行第 $j$ 列填入 $T_{i,j}$ 的值。

表3.1：各物品的体积和价值

物品	体积	价值
$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,G_2,G_3,G_4$ 的元素。

b) 给出 $W_j\ (j=0,\ldots,8)$ 的各个值。

c) 写出表3.2中①～⑥应填入的值。

d) 对于 $G_4$ 和 $W_5,W_6,W_7,W_8$，分别求出背包问题解 $S_{4,5},S_{4,6},S_{4,7},S_{4,8}$ 中物品的组合及价值总和。

2)

按如下方式归纳定义语言 $\omega$ 的项。

• 常量符号 $S,K,I$ 是 $\omega$ 的项。
• 当 $x,y$ 是 $\omega$ 的项时，$(x\cdot y)$ 是 $\omega$ 的项。
• 只有按上述方式定义的对象才是 $\omega$ 的项。

运算符 $\cdot$ 是左结合的，为使书写简洁，可以省略运算符 $\cdot$。也就是说，当 $x,y,z\in\omega$ 时，$((x\cdot y)\cdot z)$ 可以写成 $xyz$，$(x\cdot(y\cdot z))$ 可以写成 $x(yz)$。

接下来对 $x,y,z\in\omega$，将 $S,K,I$ 各自的计算规则（从左边到右边的变换规则）定义如下：

$$\begin{aligned} Ix&\Rightarrow x,\\ Kxy&\Rightarrow x,\\ Sxyz&\Rightarrow xz(yz),\\ x\Rightarrow x'\quad&\text{则}\quad xy\Rightarrow x'y,\\ y\Rightarrow y'\quad&\text{则}\quad xy\Rightarrow xy'. \end{aligned}$$

使用上述计算规则变换 $\omega$ 的项，称为归约。当无法进一步变换时，归约停止。不能进一步归约的项称为正规形。下面给出归约的例子。

$$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\in\omega$，$SKKx$ 与 $Ix$ 的归约结果相同。

b) 将 $T,F$ 定义为

$$T=K,\qquad F=KI.$$

将下面的式 (i)(ii) 归约到正规形。假定 $x,y$ 为正规形。除归约结果外，还要写出求得正规形的过程。

(i) $Txy$

(ii) $Fxy$

c) 进一步定义 $\lor,\land,\neg$ 如下：

$$\begin{aligned} \lor&=SI(KT),\\ \land&=SS(K(KF)),\\ \neg&=S(SI(KF))(KT). \end{aligned}$$

由此，对任意 $x,y\in\omega$ 有

$$\begin{aligned} \lor xy&=SI(KT)xy\Rightarrow Ix(KTx)y\\ &\Rightarrow x(KTx)y\Rightarrow xTy,\\[4pt] \land xy&=SS(K(KF))xy\Rightarrow Sx(K(KF)x)y\\ &\Rightarrow xy(K(KF)xy)\Rightarrow xy(KFy)\Rightarrow xyF,\\[4pt] \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)(iv)(v)(vi) 归约到正规形。除归约结果外，还要写出求得正规形的过程。

(iii) $\lor(\neg T)T$

(iv) $\lor(\neg T)F$

(v) $\land(\neg F)T$

(vi) $\land(\neg F)F$

Kai

1)

a)

$$\begin{gathered}G_1=\{g_1\},\\ G_2=\{g_1,g_2\},\\ G_3=\{g_1,g_2,g_3\},\\ G_4=\{g_1,g_2,g_3,g_4\}.\end{gathered}$$

b)

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

c)

$$\begin{gathered}(1)=0,\quad(2)=0,\quad(3)=12,\\(4)=13,\quad(5)=13,\quad(6)=18.\end{gathered}$$

例えば容量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\\&\qquad=KITT\Rightarrow IT\Rightarrow T=\boxed K,\\ \text{(iv)}\quad\lor(\neg T)F&\Rightarrow^*\lor FF\Rightarrow^*FTF\\&\qquad=KITF\Rightarrow IF\Rightarrow F=\boxed{KI},\\ \text{(v)}\quad\land(\neg F)T&\Rightarrow^*\land TT\Rightarrow^*TTF\\&\qquad=KTF\Rightarrow T=\boxed K,\\ \text{(vi)}\quad\land(\neg F)F&\Rightarrow^*\land TF\Rightarrow^*TFF\\&\qquad=KFF\Rightarrow F=\boxed{KI}. \end{aligned}$$

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