Knapsack problem

knapsack은 한국어로 배낭을 의미한다.

maximum weight $b$를 담을 수 있는 배낭, knapscak을 생각한다. 그리고 $n$개의 아이템을 생각하고, $i$ 아이템은 무게가 $a_i$이다. $i$ 아이템을 $x_i$개 담으면서 모든 아이템들의 무게의 합이 knapsack의 총 용량 $b$가 넘지 않도록 설계해야 한다, 즉, $\sum^n_{i=1}a_ix_i\leq b$이다.

다음과 같은 집합을 생각해보자:

$$K=\{ x\in \{0,1\}^n : \sum^n_{i=1}a_ix_i\leq b\}.$$

 

Minimal cover는 다음과 같이 정의된다:

$$\sum_{i \in C \notin \{ j \} } a_i \leq b, \quad  \forall j \in C.$$

Minimal cover로 정의되는 다음 집합을 생각해보자:

$$K^C=\{  x \in \{0,1\}^n : \sum_{i\in C} x_i \leq |C|-1 \text{for every minimla cover}\; C \; \text{for} K\}$$

Propositiion 2.1 집합 $K$ and $K^C$은 일치한다.

증명 :
$C$가 $K$의 minimal cover라면, $\sum_{i\in C} x_i \leq |C|-1$이다. 그리고 $\sum_{i=1}^n a_ix_i\leq b$가 $K^C$의 원소에 대해 성립한다.

$\bar{x}\in K^C$라고 하고 $J:=\{ j : \bar{x}_j=1\}$이라고 하자.  $\sum^n_{i=1}a_i\bar{x}_i>b$가 성립하는 $J$의 minimal subset을 $C$라고 하면, $C$는 minimal cover이고 $\sum_{i\in C}\bar{x}_i=|C|$이다.