Knapsack
2020-1ํ๊ธฐ, ๋ํ์์ โ์๊ณ ๋ฆฌ์ฆโ ์์ ์ ๋ฃ๊ณ ๊ณต๋ถํ ๋ฐ๋ฅผ ์ ๋ฆฌํ ๊ธ์ ๋๋ค. ์ง์ ์ ์ธ์ ๋ ํ์์ ๋๋ค :) ์ ์ฒด ํฌ์คํธ๋ Algorithm ํฌ์คํธ์์ ํ์ธํ์ค ์ ์์ต๋๋ค.
ps) โknapsackโ์ ๋ป์ โํ์ดํน ๋ฐ์์ ์์ฃผ ๊ฐ๋จํ ์คํฌ์ธ ์ ์ฌ์ฉ๋๋ ์์ ๋ฅ์โ์ด๋ผ๊ณ ํ๋ค. ์ด๊ณณ์ ๋ฅ์์ ๋ํด ์ ์ค๋ช ์ด ๋์ด ์์ผ๋, ๊ถ๊ธํ ์ฌ๋์ ํ๋ฒ ์ฝ์ด๋ณด์ ๐
๋ฌธ์ ์ ์Permalink
๋๋์ด ๋ณด์๊ฐ๊ฒ์ ๋ฐฐ๋ญ์ ๋ฉ๊ณ ์นจ์ ํ๋ค. ๋ฐฐ๋ญ์ ์ต๋ ์ฉ๋์ W์ด๋ฉฐ, ์ด๋ฅผ ์ด๊ณผํด์ ๋ณด์์ ๋ด์ผ๋ฉด ๋ฐฐ๋ญ์ด ์ฐข์ด์ง ๊ฒ์ด๋ค. ๊ฐ ๋ณด์๋ค์ ๋ฌด๊ฒ์ ๊ฐ๊ฒฉ์ ์๊ณ ์๋ค. ๋ฐฐ๋ญ์ด ์ฐข์ด์ง์ง ์๋ ์ ์์ ๊ฐ๊ฒฉ ํฉ์ด ์ต๋๊ฐ ๋๋๋ก ๋ณด์์ ๋ด๋ ๋ฐฉ๋ฒ์?
์์ ๊ฐ์ด <๋
์; knapsack> ๋ฌธ์ ๋ ์ ํํ ์ต๋ ์ฉ๋, Capacity ์๋์์ ๋ด๊ธด ๊ฐ์ ํฉ์ด ์ต๋๊ฐ ๋๋๋ก ํ๋ ์ต์ ํ ๋ฌธ์ ๋ค. ๋
์ ๋ฌธ์ ์ ๊ฒฝ์ฐ, ๋ฐฐ๋ญ์ ๋ฃ๋ ๋์์ด (1) pick w/ replacement (2) pick w/o replace (3) ๋์์ ์๋ฅผ ์ ์๋์ง(fractional knapsack)์ ๋ฐ๋ผ์ ์๊ณ ๋ฆฌ์ฆ์ด ์กฐ๊ธ์ฉ ๋ฌ๋ผ์ง๋ค. (1), (2)๋ฒ ๊ฒฝ์ฐ๋ DP๋ฅผ ํตํด ํด๊ฒฐํ๊ณ , (3)๋ฒ์ fractional knapsack์
Pick w/ replacementPermalink
์ฒซ๋ฒ์งธ ๊ฒฝ์ฐ๋ ์์ดํ ์ ์๊ฐ ๋ฌดํํ ๋ง์(unlimited quantities) ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค. ์ด๋, ๋ ์ ๋ฌธ์ ๋ capacity๋ฅผ 1๋ถํฐ ์ฌ๋ ค๊ฐ๋ฉฐ ์ด์ ์ ๊ณ์ฐํ ๋ ์ DP์ ๊ฐ์ ์์ดํ ์ ์ถ๊ฐํ์ ๋, ๊ฐ์ฅ ํฐ value๋ฅผ ์ ๋ํ๋ ์กฐํฉ์ ์ฐพ๋ ๋ฌธ์ ๊ฐ ๋๋ค. ์ผ๋จ ์ฝ๋๋ฅผ ์ดํด๋ณด์!!
Initialize all
for
โโ
return
์ ๋ง ๊ฐ๋จํ๋ค!!!
Pick w/o replacementPermalink
๋๋ฒ์งธ ๊ฒฝ์ฐ๋, ๋ฐฐ๋ญ์ ๋ด์ ์ ์๋ ์์ดํ ์ ์๊ฐ ์ค์ง ํ๋๋ง ์๋(only one of each item available) ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค.
์ด ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํด์ ์์ดํ
์ ๊ณ ๋ฅผ์ง ๋ง์ง๋ก sub-problem์ ์์ฑํ๋ binary choice์ ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋ค.1 ๊ทธ๋์ ์ ์ฒด
์ด๋,
1. ๋ง์ฝ ํ์ฌ ์ดํด๋ณด๋ capacity
2. ๋ง์ฝ ํ์ฌ
์์ ์๊ณ ๋ฆฌ์ฆ์ ์ฝ๋๋ก ์ฎ๊ธฐ๋ ๊ฒ์ ๊ฒฐ๊ตญ 2์ฐจ์ DP ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ๊ณผ ๊ฐ๋ค! ์ฝ๋๋ฅผ ์ดํด๋ณด์!
Initialize all
for
โโfor
โโโโif
โโโโโโ
โโโโelse
โโโโโโ
return

2์ฐจ์ DP์ ๋ชจ์ต์ ๊ทธ๋ ค๋ณด๋ฉด ์๋ฐ ๋๋์ผ๋ก DP ๋ฐฐ์ด์ด ์ฑ์์ง๋ค
๋งบ์๋งPermalink
๋ณธ์ธ์ PS ๊ฒฝํ์, ๋ ์ ๋ฌธ์ ์์ ๋ช ํํ ์ ์ ์๋ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฑด ์ด๋ ต์ง ์๋ค. ํ์ง๋ง, ๋ ์ ๋ฌธ์ ์ธ์ง ์ ํ ๋ชจ๋ฅด๊ฒ ๋๋ฐ, ์ฌ์ค์ ๋ ์์ผ๋ก ํ์ด์ผ ๋๋ ๋ฌธ์ ๋ค์ด ์ข ์ข ์๋ค. ์๋ฅผ ๋ค๋ฉด 2019 ICPC ํ๊ตญ ์์ 1๋ฒ ๋ฌธ์ ์ธ 17528๋ฒ: Two Machines๊ฐ ๋ ์์ธ์ง ํ๋จํ๋๊ฒ ์ฝ์ง ์์ ๊ทธ๋ฐ ๋ฌธ์ ์๋ค.
์ถ์ฒ ๋ฌธ์ Permalink
- 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ
- 1450๋ฒ: ๋ ์๋ฌธ์ โ ํ๋ฒํ ๋ ์ ๋ฌธ์ ์ฒ๋ผ ๋ณด์ด์ง๋ง, ๊ฝค Hard ํ๋ค ๐ค
- 12920๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ2 โ ์ฝ๊ฐ์ ๋ณํ๊ณผ ํจ๊ป, ๋ถํ ์ ๋ณต ํ ํฌ๋์ ํ๋ ๋ ์จ์ผ ํ๋ ๋ฌธ์ ๋ค ๐บ
- ๋ ์ ์นดํ ๊ณ ๋ฆฌ์ ๋ฌธ์ ๋ชจ์
์ฐธ๊ณ ์๋ฃPermalink
-
๋๋ค๋ฅธ DP ๋ฌธ์ ์ธ Weighted Interval Scheduling์์๋ binary choice ๊ธฐ๋ฒ์ ์ฌ์ฉํ์๋ค! โฉ