DP knapsack ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ฐฐ๋‚ญ ๋ฌธ์ œ

๋ฐฐ๋‚ญ ๋ฌธ์ œ๋Š” n๊ฐœ์˜ ๋ฌผ๊ฑด๊ณผ ๋ฐฐ๋‚ญ์ด ์žˆ์„ ๋•Œ (๋ฌผ๊ฑด์—๋Š” ๊ฐ€์น˜์™€ ๋ฌด๊ฒŒ๊ฐ€ ์กด์žฌํ•œ๋‹ค), ๋ฐฐ๋‚ญ์˜ ์ตœ๋Œ€ ์šฉ๋Ÿ‰์„ ์ดˆ๊ณผํ•˜์ง€ ์•Š์œผ๋ฉด์„œ ๋ฐฐ๋‚ญ์— ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๊ฐ€์น˜์˜ ํ•ฉ์„ ์ฐพ๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋ฐฐ๋‚ญ ๋ฌธ์ œ๋Š” ๋ฌผ๊ฑด์„ ์ชผ๊ฐค ์ˆ˜ ์žˆ๋Š” Fraction Knapsack Proplem ๊ณผ ๋ฌผ๊ฑด์„ ์ชผ๊ฐค ์ˆ˜ ์—†๋Š” 0-1 Knapsack Problem ์œผ๋กœ ๋‚˜๋‰œ๋‹ค. ์ด ๊ธ€์—์„œ ์ •๋ฆฌํ•œ ๊ฒƒ์€ 0-1 Kanpsack Problem ์ด๋‹ค.

๋ฐฐ๋‚ญ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด DP์ธ ์ด์œ 

ํ•ด๋‹น ๋ฌธ์ œ๊ฐ€ ์ตœ๋Œ€ ์ด์ต์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋ผ๊ณ ๋Š” ํ•ด๋„, ๊ฒฐ๊ตญ ๋ณธ์งˆ์€ ๋ฌผ๊ฑด์„ ๋ฐฐ๋‚ญ์— ๋„ฃ๋А๋ƒ, ๋งˆ๋А๋ƒ์ด๋‹ค. ๋งŒ์•ฝ ์ตœ๋Œ€ Mkg๊นŒ์ง€ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฐ๋‚ญ์ด ์žˆ๊ณ  Nkg์˜ ๋ฌผ๊ฑด์ด ์žˆ์„ ๋•Œ, ์šฐ๋ฆฌ์˜ ์„ ํƒ์ง€๋Š” ๋‘ ๊ฐ€์ง€ ๋ฟ์ด๋‹ค. ๋ฌผ๊ฑด์„ ๋„ฃ์–ด์„œ ๊ฐ€๋ฐฉ ์ƒํƒœ๊ฐ€ (M-N)kg ์ด ๋˜๊ฑฐ๋‚˜, ๊ทธ๋Œ€๋กœ Mkg ์ด๊ฑฐ๋‚˜โ€ฆ ๋‹จ์ˆœํžˆ ์ด ๊ณผ์ •์„ ๋ชจ๋“  ๋ฌผ๊ฑด์— ๋Œ€ํ•ด ๋ฐ˜๋ณตํ•˜๋Š”๊ฑฐ๋‹ค. ๊ฐ€๋ฐฉ์— ๋” ์ด์ƒ ๊ณต๊ฐ„์ด ๋‚จ์ง€ ์•Š์„ ๋•Œ๊นŒ์ง€ !

๊ทธ๋ ‡๋‹ค๋ฉด ๋” ๋‚˜์•„๊ฐ€์„œ ์ƒ๊ฐ์˜ ์ „ํ™˜์„ ํ•ด๋ณด์ž. ์กฐ๊ธˆ ๋” ๊ตฌ์ฒด์ ์ธ ์˜ˆ์‹œ๋กœ, 6kg ๊นŒ์ง€ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๊ฐ€๋ฐฉ์— 3kg ์„ ๊ฐ€์ง„ ๋ฌผ๊ฑด์„ ๋„ฃ์—ˆ๋‹ค๊ณ  ํ•ด๋ณด์ž. ์—ฌ๊ธฐ์„œ 3kg ์€ ๋ฌด์กฐ๊ฑด ๋„ฃ์–ด์•ผ ํ•˜๋Š” ๋ฌผ๊ฑด์ด๋ผ๊ณ  ์น˜๊ณ , ๊ทธ๋ ‡๋‹ค๋ฉด ๋‚จ์€ ๊ณต๊ฐ„ 3kg ์— ๋‚˜๋จธ์ง€ ๋ฌผ๊ฑด์„ ๋„ฃ์–ด์•ผ ํ•˜๋Š” ์ƒˆ๋กœ์šด ๋ฌธ์ œ๋กœ ์น˜ํ™˜ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋ฅผ ํ•œ ๋ฒˆ ๋” ์ง„ํ–‰ํ•ด ๋ณด๋ฉด, 1kg ๋ฌผ๊ฑด์„ ๋„ฃ์–ด๋ณด์ž. ๊ทธ๋Ÿฌ๋ฉด ๋‚จ์€ ๊ณต๊ฐ„ 2kg ์— ๋‚˜๋จธ์ง€ ๋ฌผ๊ฑด์„ ๋„ฃ์–ด์•ผ ํ•˜๋Š” ์ƒˆ๋กœ์šด ๋ฌธ์ œ๊ฐ€ ๋งŒ๋“ค์–ด์ง„๋‹ค. ์ฆ‰ ์•„๋ž˜์™€ ๊ฐ™์€ ์ˆ˜์‹์ด ๋œ๋‹ค.

์ตœ๋Œ€ 6kg ๋ฅผ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฐ๋‚ญ์˜ ๊ฐ€์น˜
= 3kg + (์ตœ๋Œ€ 3kg ๋ฅผ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฐ๋‚ญ์˜ ๊ฐ€์น˜)
= 1kg + (์ตœ๋Œ€ 2kg ๋ฅผ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฐ๋‚ญ์˜ ๊ฐ€์น˜)
...

์ž‘์€ ๋ถ€๋ถ„์˜ ๋‹ต์ด ํฐ ๋ถ€๋ถ„์˜ ๋‹ต์ด ๋˜๋Š” DP ์˜ ํŠน์ง•์ด ๋‚˜ํƒ€๋‚œ๋‹ค. ์ฆ‰ ๋ฐฐ๋‚ญ ๋ฌธ์ œ๋Š” DP ๋กœ ํ’€์–ด๋‚ผ ์ˆ˜ ์žˆ๋‹ค !

์ˆ˜์‹์œผ๋กœ ์ ‘๊ทผ

์œ„์—์„œ ๋˜‘๊ฐ™์€ ๋กœ์ง์„ ๋ฐ˜๋ณตํ•  ๋•Œ ๋ณ€ํ•˜๋Š” ๊ฒƒ์€ ๋ฐฐ๋‚ญ์˜ ๋ฌด๊ฒŒ, ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜ 2๊ฐ€์ง€์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์ด์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฐ ๊ฒฝ์šฐ์˜ ์ˆ˜์— ๋”ฐ๋ฅธ ๋‹ต์„ ์ €์žฅํ•ด์ค˜์•ผ ํ•œ๋‹ค.

์ตœ๋Œ€์ด์ต[i][w] = ์ตœ๋Œ€๋ฌด๊ฒŒ๊ฐ€ w์ธ ๋ฐฐ๋‚ญ์—์„œ i๋ฒˆ์งธ ๋ฌผ๊ฑด๊นŒ์ง€ ๋„ฃ์—ˆ์„ ๋•Œ ์ตœ๋Œ€ ๊ฐ€์น˜
Ex. ์ตœ๋Œ€์ด์ต[4][6] = ์ตœ๋Œ€ ๋ฌด๊ฒŒ 6kg์ธ ๋ฐฐ๋‚ญ์—์„œ 4๋ฒˆ์งธ ๋ฌผ๊ฑด๊นŒ์ง€ ๋„ฃ์—ˆ์„ ๋•Œ์˜ ๊ฐ€์น˜ = 8$

์ด์ œ ์ผ๋ฐ˜ํ™”ํ•ด๋ณด์ž. ์ผ๋‹จ ์ฒ˜์Œ ์„ ํƒ์—์„œ 2๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์žˆ๋‹ค.

  1. ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ๊ฐ€ ๋ฐฐ๋‚ญ์˜ ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋ฅผ ์ดˆ๊ณผํ•  ๋•Œ.

    ์• ์ดˆ์— ์ด ๊ฒฝ์šฐ์—๋Š” ๋ฐฐ๋‚ญ์— ๋ฌผ๊ฑด์„ ๋„ฃ์„ ์ˆ˜ ์—†๋‹ค. ์•„๋ฌด๋Ÿฐ ๋ณ€๊ฒฝ์ ์ด ์—†๊ณ , k+1 ๊นŒ์ง€ ์ง„ํ–‰ํ–ˆ์œผ๋ฏ€๋กœ dp[K+1][W] = dp[K][W] ๋œ๋‹ค. (์—ฌ๊ธฐ์„œ dp[K][W] ๋Š” ๊ธฐ์กด์— ๊ณ„์‚ฐํ•ด๋‘” ์ตœ๋Œ€ ๊ฐ€์น˜๋ฅผ ๋งํ•œ๋‹ค.)

  2. ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ๊ฐ€ ๋ฐฐ๋‚ญ์˜ ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋ฅผ ์ดˆ๊ณผํ•˜์ง€ ์•Š์„ ๋•Œ.

    ์ด ๊ฒฝ์šฐ์—๋Š” ์„ ํƒ์— ๋”ฐ๋ผ ๋‹ค์‹œ 2๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์žˆ๋‹ค.

    2-1 ๋„ฃ์ง€ ์•Š๋Š”๋‹ค.

    ์ด ๊ฒฝ์šฐ๋Š” 1๋ฒˆ์˜ ๊ฒฐ๊ณผ์™€ ๊ฐ™๋‹ค. dp[K+1][W] = dp[K][W]

    2-2 ๋„ฃ๋Š”๋‹ค.

    ์—ฌ๊ธฐ์„œ๋Š” ์ƒ๊ฐํ•ด๋ด์•ผํ•œ๋‹ค. ๋งŒ์•ฝ ์ตœ๋Œ€ 6kg์ธ ๋ฐฐ๋‚ญ์— ์ฒซ ๋ฒˆ์งธ๋กœ 3kg ๋ฌผ๊ฑด(4$)์„ ๋„ฃ์—ˆ๋‹ค๊ณ  ์นœ๋‹ค๋ฉด dp[1][6] = 4 + dp[0][3] ์ด ๋œ๋‹ค. ์ด๋ฅผ ์ผ๋ฐ˜ํ™”ํ•ด์„œ ์ตœ๋Œ€ Wkg๊นŒ์ง€ ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฐ๋‚ญ์ด K+1 ๋ฒˆ์งธ ๋ฌผ๊ฑด์„ ๋‹ด์•˜์„ ๋•Œ๊ฐ€ ์ตœ๋Œ€ ๊ฐ€์น˜๋ผ๋ฉด dp[K+1][W] = (K+1๊ฐ€์น˜) + dp[K][W-M] ์ด ๋œ๋‹ค. ํ•ด์„ํ•˜์ž๋ฉด (K+1 ๋ฒˆ์งธ ๋ฌผ๊ฑด์˜ ๊ฐ€์น˜) + (๊ทธ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ M์„ ๋บ€ (W-M)kg ์œผ๋กœ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋”ฐ์ ธ์„œ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๊ฐ€์น˜) = ์ตœ์ข… ๊ฒฐ๊ณผ๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.

์ ํ™”์‹

์ƒ๊ฐํ•ด๋ณผ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ 3๊ฐ€์ง€ ์žˆ์—ˆ๋Š”๋ฐ, ์ด๋ฅผ ์ˆ˜์‹์œผ๋กœ ์ •๋ฆฌํ•ด๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  1. ๋ฌผ๊ฑด K์˜ ๋ฌด๊ฒŒ > ๋ฐฐ๋‚ญ W์˜ ๋ฌด๊ฒŒ : dp[K][W] = dp[K-1][W]

  2. ๋ฌผ๊ฑด K์˜ ๋ฌด๊ฒŒ <= ๋ฐฐ๋‚ญ W์˜ ๋ฌด๊ฒŒ : dp[K][W] = max(dp[K-1][W], ๋ฌผ๊ฑด K์˜ ๊ฐ€์น˜ + dp[K-1][W-K])