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๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ์๋ค.
๋ฌผ๊ฑด์ ๋ฌด๊ฒ๊ฐ ๋ฐฐ๋ญ์ ์ต๋ ๋ฌด๊ฒ๋ฅผ ์ด๊ณผํ ๋.
์ ์ด์ ์ด ๊ฒฝ์ฐ์๋ ๋ฐฐ๋ญ์ ๋ฌผ๊ฑด์ ๋ฃ์ ์ ์๋ค. ์๋ฌด๋ฐ ๋ณ๊ฒฝ์ ์ด ์๊ณ , k+1 ๊น์ง ์งํํ์ผ๋ฏ๋ก
dp[K+1][W] = dp[K][W]
๋๋ค. (์ฌ๊ธฐ์ dp[K][W] ๋ ๊ธฐ์กด์ ๊ณ์ฐํด๋ ์ต๋ ๊ฐ์น๋ฅผ ๋งํ๋ค.)๋ฌผ๊ฑด์ ๋ฌด๊ฒ๊ฐ ๋ฐฐ๋ญ์ ์ต๋ ๋ฌด๊ฒ๋ฅผ ์ด๊ณผํ์ง ์์ ๋.
์ด ๊ฒฝ์ฐ์๋ ์ ํ์ ๋ฐ๋ผ ๋ค์ 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๊ฐ์ง ์์๋๋ฐ, ์ด๋ฅผ ์์์ผ๋ก ์ ๋ฆฌํด๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
๋ฌผ๊ฑด K์ ๋ฌด๊ฒ > ๋ฐฐ๋ญ W์ ๋ฌด๊ฒ :
dp[K][W] = dp[K-1][W]
๋ฌผ๊ฑด K์ ๋ฌด๊ฒ <= ๋ฐฐ๋ญ W์ ๋ฌด๊ฒ :
dp[K][W] = max(dp[K-1][W], ๋ฌผ๊ฑด K์ ๊ฐ์น + dp[K-1][W-K])