์๊ณ ๋ฆฌ์ฆ/๐๏ธ ์ ๋ฆฌ
DP - Knapsack (๋ฐฐ๋ญ๋ฌธ์ )
https://www.acmicpc.net/problem/12865 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ ์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 โค N โค 100)๊ณผ ์ค์๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ K(1 โค K โค 100,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑฐ์ณ ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W(1 โค W โค 100,000)์ ํด๋น ๋ฌผ๊ฑด์ ๊ฐ์น V(0 โค V โค 1,000) www.acmicpc.net ๐น๏ธ Knapsack ์๊ณ ๋ฆฌ์ฆ ๊ณผ์ DP ๋ฌธ์ ์ค ํ๋๋ก, ๋ฐฐ๋ญ์ ํฌ๊ธฐ k์ n๊ฐ์ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ(w)์ ๊ฐ์น(v)๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ๋ฐฉ์ ๋ฌผ๊ฑด์ k์ ๋์ง ์๋๋ก ๋ฃ๊ณ ์ต๋ ๊ฐ์น์ ํฉ์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ex) ๋ฐฐ๋ญ์ ํฌ๊ธฐ๋ k์ด๊ณ , 5๊ฐ์ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ์ ๊ฐ์น๊ฐ ๋ค์๊ณผ ๊ฐ์ด ์ฃผ์ด์ก์ ๋, ์ต๋ ๊ฐ์น์ ํฉ์ ๊ตฌํ๊ธฐ ๋ฌผ๊ฑด 1 : w =..