tags: `ADA 6.5`

ADA 6.5: Knapsack Problem 背包問題

前言

Input：n items where
$i$ -th item has value
$v_{i}$ and weighs
$w_{i}$ (
$v_{i}$ and
$w_{i}$ are positive integers)
Output：the maximum value for the knapsack with capacity of
$W$

猴子中文翻譯
Input 就是他有 n 個 items(有n個東西你可以選擇要不要裝進去)，每個 item 都有它的 value
$v_{i}$ 和他的 weighs
$w_{i}$ （可以想像 value 是價值，weighs 是重量）
我們要讓 value 也就是包包裡面裝了越多價值的東西越好，但是我們包包會有它的限制就是
$W$

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Variants of knapsack problem 變形背包問題
- 0-1 Knapsack Problem (每項物品只能拿一個 EX: 拿 or 不拿)
- Unbounded Knapsack Problem (每項物品可以重複拿很多個)
- Multidimensional Knapsack Problem (背包空間有限
  $W$ )
- Multiple-Choice Knapsack Problem (每一類物品最多拿一個)
- Fractional Knapsack Problem (物品可以只拿部分 EX: 可以切一半的東西我只拿一半 0.5 之類的)

0-1 Knapsack Problem

Input:

n

items where

i

-th item has value

v_{i}

and weighs

w_{i}

Output: the max value within

W

capacity, where each item is chosen at most once

不拿物品，或是只拿一個的狀況。

Step 1: Characterize an OPT Solution

Subproblems ZO-KP(
$i, w$ )
- ZO-KP(
  $i, w$ ): 0-1 knapsack proble within
  $w$ capacity for the first
  $i$ items
  考慮
  $i$ items 然後 capacity 剩下
  $w$ 的狀況
  這句我反覆咀嚼，好像懂了又好像沒有懂
  Andy: 假設你可以背10kg，拿了一個3kg的水，剩下7kg的預算還可以使用。這裡的3kg就是w
- Goal: ZO-KP(
  $n, W$ )
  目標就是要找到這個 n 和 W 的值
  這裡的Ｗ和上面 w 有什麼不一樣？
  Andy:承上題 W = (w == 10kg)
Optimal substructure: suppose OPT is an optimal solution to ZO-KP(i, w), there are 2 cases:(拿跟不拿的 case)
- Case 1: item
  $i$ in OPT
  - OPT{
    $i$ } is an optimal solution of ZO-KP(i - 1, w - w_i)
$M_{i, w}$ =
$v_{i}$ +
$M_{i - 1, w - w_{i}}$
- Case 2: item
  $i$ not in OPT
  - OPT is an optimal solution of ZO-KP(i - 1, w )
$M_{i, w}$ =
$M_{i - 1, w}$

Step 2: Recursively Define the Value of an OPT Solution

Recursively define the value

$M_{i, w} = {\begin{cases} 0, & if i =0 \\ M_{i - 1, w}, & if w_{i} > w \\ m a x ([v_{i} + M_{i - 1, w - w_{i}}], M_{i - 1, w}), & otherwise \end{cases}$

Step 3: Compute Value of an OPT Solution

item List

$i$	$w_{i}$	$v_{i}$
1	1	4
2	2	9
3	4	20

W

= 5

table:

i\w	1	2	3	4	5
0	0	0	0	0	0
1	4	4	4	4	4
2	4	9	13	13	13
3	4	9	13	20	24

Unbounded Knapsack Problem

Input:

n

items where

i

-th item has value

v_{i}

and weighs

w_{i}

has unlimted supplies
Output: the max value within

W

capacity

沒有限制可以拿幾個物品的狀況。

Step 1: Characterize an OPT Solution

Subproblems
- U-KP(
  $i$ ,
  $w$ ): unbounded knapsack proble within
  $w$ capacity for the first
  $i$ items
- ~~Goal:~~ U-KP(
  $n$ ,
  $W$ )
Time complexity =
$Θ (n^{2} W)$ , not a good solution.
因為不用再考慮拿過不能再拿的狀況
所以就不用再考慮
$i$
- U-KP(
  $w$ ): unbounded knapsack proble within
  $w$ capacity for the first
  $i$ items
- Goal:U-KP(
  $W$ )
Optimal substructure: suppose OPT is an optimal solution to U-KP(
$w$ ), there are n cases:
- Case 1: item
  $1$ in OPT
  - Removing an item 1 from OPT is an optimal solution of U-KP(
    $w - w_{1}$ )
- Case 2: item
  $2$ in OPT
  - Removing an item 2 fromOPT is an optimal solution of U-KP(
    $w - w_{2}$ )
- …
- Case n: item
  $n$ in OPT
$M_{w} = v_{i} + M_{w - w_{i}}$

Step 2: Recursively Define the Value of an OPT Solution

Recursively define the value

$M_{i, w} = {\begin{cases} 0, & if w =0 or w_{i} > w for all i \\ m a x_{(1 \leq i \leq n, w_{i} \leq w)} (v_{i} + M_{w - w_{i}}), & otherwise \end{cases}$

Step 3: Compute Value of an OPT Solution

item List

$i$	$w_{i}$	$v_{i}$
1	1	4
2	2	9
3	4	17

W

= 5

table:

$w$	0	1	2	3	4	5
$M [w]$	0	4	9	13	18	22

w_{1} = m a x (4 + 0)

w_{2} = m a x (4 + 4, 9 + 0)

w_{3} = m a x (4 + 9, 9 + 4)

w_{4} = m a x (4 + 13, 9 + 9, 17 + 0)

w_{5} = m a x (4 + 18, 9 + 13, 17 + 4)

Multidimensional Knapsack Problem

Input:

n

items where

i

-th item has value

v_{i}

and weighs

w_{i}

and size

d_{i}

Output: the max value within

W

capacity and with the size of

D

, where each item is chosen at most once

Step 1: Characterize an OPT Solution

Subproblems
- M-KP(
  $i, w, d$ ): multidimensional knapsack proble within
  $w$ capacity and
  $d$ size for the first
  $i$ items
- Goal: M-KP(
  $n, W, D$ )
Optimal substructure: suppose OPT is an optimal solution to M-KP(
$i, w, d$ ), there are 2 cases:
- Case 1: item
  $i$ in OPT
  - OPT{
    $i$ } is an optimal solution of M-KP(
    $i - 1, w - w_{i}, d - d_{i}$ )
- Case 2: item
  $i$ not in OPT
  - OPT is an optimal solution of M-KP(
    $i - 1, w, d$ )

Step 2: Recursively Define the Value of an OPT Solution

Recursively define the value

$M_{i, w} = {\begin{cases} 0, & if i =0 \\ M_{i - 1, w, d}, & if w_{i} > w or d_{i} > d \\ m a x ([v_{i} + M_{i - 1, w - w_{i}, d - d_{i}}], M_{i - 1, w, d}), & otherwise \end{cases}$

Step 3: Compute Value of an OPT Solution

item List

$i$	$w_{i}$	$v_{i}$	$d_{i}$
1	1	4	2
2	2	9	4
3	4	20	1

W

= 4

D

= 6

table:

d

= 0

i\w	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	0

d

= 1

i\w	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	20

d

= 2

i\w	1	2	3	4
0	0	0	0	0
1	4	4	4	4
2	4	4	4	4
3	4	4	4	20

d

= 3

i\w	1	2	3	4
0	0	0	0	0
1	4	4	4	4
2	4	4	4	4
3	4	4	4	20

d

= 4

i\w	1	2	3	4
0	0	0	0	0
1	4	4	4	4
2	4	9	9	9
3	4	9	9	20

d

= 5

i\w	1	2	3	4
0	0	0	0	0
1	4	4	4	4
2	4	9	9	9
3	4	9	9	20

d

= 6

i\w	1	2	3	4
0	0	0	0	0
1	4	4	4	4
2	4	9	13	13
3	4	9	13	20

Multiple-Choice Knapsack Problem

Input:

n

items
*

v_{i, j}

: value of

j

-th item in the group

i

w_{i, j}

: weight of

j

-th item in the group

i

n_{i}

: number of items in group

i

n

: total number of items

(Σ n_{i})

G

: total number of groups

Output: the maximum value for the knapsack with capacity of

W

, where the item from each group can be selected at most once

一個群組只能拿一個的狀況

Step 1: Characterize an OPT Solution

Subproblems
- MC-KP(
  $w$ ):
  ~~$w$ capacity~~
- MC-KP(
  $i, w$ ):
  $w$ capacity for the first
  $i$ groups
- MC-KP(
  $i, j, w$ ):
  $w$ capacity for the first j items from first
  $i$ groups
- Goal: MC-KP(
  $G, W$ )
Optimal substructure: suppose OPT is an optimal solution to MC-KP(
$i, w$ ), for the group
$i$ , there are
$n_{i} + 1$ cases:
- Case 1: no item from
  $i$ -th group in OPT
  - OPT{
    $i$ } is an optimal solution of MC-KP(
    $i - 1, w$ )
- Case j+2:
  $j$ -th item from
  $i$ -th group (
  $i t e m_{i, j}$ ) in OPT
  - OPT (
    $i t e m_{i, j}$ ) is an optimal solution of MC-KP(
    $i - 1, w - w_{i, j}$ )

Step 2: Recursively Define the Value of an OPT Solution

Recursively define the value

$M_{i, w} = {\begin{cases} 0, & if i =0 \\ M_{i - 1, w}, & if w_{i, j} > w for all j d \\ m a x_{1 \leq j \leq n_{i}} ([v_{i, j} + M_{i - 1, w - w_{i, j}}], M_{i - 1, w}), & otherwise \end{cases}$

Step 3: Compute Value of an OPT Solution

這題老師就沒有舉例了

複雜度計算蠻有趣的，所以就記下來了。

\sum_{i = 1}^{G} \sum_{w = 0}^{W} \sum_{j = 1}^{n_{i}} c = c \sum_{w = 0}^{W} \sum_{i = 1}^{G} \sum_{j = 1}^{n_{i}} 1 = c \sum_{w = 0}^{W} n = c n W

⇓

T (n) = Θ (n W)

Fractional Knapsack Problem

可以隨便分割物品的狀況

簡單到我就不做筆記了

找到CP值最高的那個物品，就拿到滿就好了

tags: ADA 6.5

ADA 6.5: Knapsack Problem 背包問題

前言

0-1 Knapsack Problem

Step 1: Characterize an OPT Solution

Step 2: Recursively Define the Value of an OPT Solution

Step 3: Compute Value of an OPT Solution

Unbounded Knapsack Problem

Step 1: Characterize an OPT Solution

Step 2: Recursively Define the Value of an OPT Solution

Step 3: Compute Value of an OPT Solution

Multidimensional Knapsack Problem

Step 1: Characterize an OPT Solution

Step 2: Recursively Define the Value of an OPT Solution

Step 3: Compute Value of an OPT Solution

Multiple-Choice Knapsack Problem

Step 1: Characterize an OPT Solution

Step 2: Recursively Define the Value of an OPT Solution

Step 3: Compute Value of an OPT Solution

Fractional Knapsack Problem

Read more

Modular Mojo 讀書會

Week10 (May 20)

ADA 1.1 Introduction

leetcode刷題讀書會行前須知

tags: `ADA 6.5`