0-1 Knapsack
-
[BaekJoon] 12865๋ฒ : ํ๋ฒํ ๋ฐฐ๋ญSW Test/BaekJoon 2021. 4. 20. 02:07
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด ๋ฌธ์ ๋ฅผ ๊ทธ๋ฆฌ๋๋ผ๊ณ ์คํดํ์ฌ ์ค๋ ๋๋น ๊ฐ์น๊ฐ ๊ฐ์ฅ ํฐ ๊ฒฝ์ฐ๋ฅผ ๋ฃ๋๋ค๊ณ ํ ๊ฒฝ์ฐ ์์ธ๊ฐ ๋ฐ์ํ๊ฒ ๋ฉ๋๋ค. ๊ทธ๋ฆฌ๋๊ฐ ์๋ DP๋ก ํด๊ฒฐํด์ผ ํ๋ฉด DP๋ก ์ ๋ช ํ 0-1 knapsack ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. D[i][w] : ํ์ฌ w ๋ฌด๊ฒ๊ฐ ๋จ์ ์ํ์์ i๋ฒ์งธ item์ ํ๊น์ง ์ต๋ ๊ฐ์น if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i๋ฒ์งธ Item์ ๋ด์ ์ ์๋ค๋ฉด, i-1๋ฒ์งธ๊น์ง Item์ ๋ด์ผ๋ฉด์ ํ์ฌ ๋ด์ ์ ์๋ ๋ฌด๊ฒ๊ฐ w-w[i]๋งํผ ๋จ์ ๊ฒฝ์ ์ ์ต๋ ๊ฐ์นํฉ์ i๋ฒ์งธ Item์ ๊ฐ์น๋ฅผ ํฉํ ๊ฐ๊ณผ D[i-1][w] ๊ฐ ๋น๊ต else, D[i][w] = D[i-1][w] #include #..