์ด ๋ฌธ์ ๋ ์์ฃผ ํ๋ฒํ ๋ฐฐ๋ญ์ ๊ดํ ๋ฌธ์ ์ด๋ค.
ํ ๋ฌ ํ๋ฉด ๊ตญ๊ฐ์ ๋ถ๋ฆ์ ๋ฐ๊ฒ ๋๋ ์ค์๋ ์ฌํ์ ๊ฐ๋ ค๊ณ ํ๋ค. ์ธ์๊ณผ์ ๋จ์ ์ ์ฌํผํ๋ฉฐ ์ต๋ํ ์ฆ๊ธฐ๊ธฐ ์ํ ์ฌํ์ด๊ธฐ ๋๋ฌธ์, ๊ฐ์ง๊ณ ๋ค๋ ๋ฐฐ๋ญ ๋ํ ์ต๋ํ ๊ฐ์น ์๊ฒ ์ธ๋ ค๊ณ ํ๋ค.
์ค์๊ฐ ์ฌํ์ ํ์ํ๋ค๊ณ ์๊ฐํ๋ N๊ฐ์ ๋ฌผ๊ฑด์ด ์๋ค. ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W์ ๊ฐ์น V๋ฅผ ๊ฐ์ง๋๋ฐ, ํด๋น ๋ฌผ๊ฑด์ ๋ฐฐ๋ญ์ ๋ฃ์ด์ ๊ฐ๋ฉด ์ค์๊ฐ V๋งํผ ์ฆ๊ธธ ์ ์๋ค. ์์ง ํ๊ตฐ์ ํด๋ณธ ์ ์ด ์๋ ์ค์๋ ์ต๋ K๋งํผ์ ๋ฌด๊ฒ๋ง์ ๋ฃ์ ์ ์๋ ๋ฐฐ๋ญ๋ง ๋ค๊ณ ๋ค๋ ์ ์๋ค. ์ค์๊ฐ ์ต๋ํ ์ฆ๊ฑฐ์ด ์ฌํ์ ํ๊ธฐ ์ํด ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์น์ ์ต๋๊ฐ์ ์๋ ค์ฃผ์.
์ ๋ ฅ
์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 โค N โค 100)๊ณผ ์ค์๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ K(1 โค K โค 100,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑฐ์ณ ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W(1 โค W โค 100,000)์ ํด๋น ๋ฌผ๊ฑด์ ๊ฐ์น V(0 โค V โค 1,000)๊ฐ ์ฃผ์ด์ง๋ค.
์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋ชจ๋ ์๋ ์ ์์ด๋ค.
์ถ๋ ฅ
ํ ์ค์ ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์นํฉ์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
2์ฐจ์ ๋ฐฐ์ด๋ก dp ์ค์ ํ, ์ต๋ ์์ฉ ๋ฌด๊ฒ์ ๋ฐ๋ผ ์กฐ๊ฑด์ ๋๋์ด์ค
dp 2์ฐจ์ ๋ฐฐ์ด, ์ต๋ ์์ฉ ๋ฌด๊ฒ์ ๋ฐ๋ผ ๋ค๋ฅธ ์กฐ๊ฑด
if(w[i] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
import java.io.*;
public class DP_8 {
static int w[],v[], dp[][], n, k;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
k = Integer.parseInt(s[1]);
w = new int[n+1];
v = new int[n+1];
dp = new int[n+1][k+1];
for(int i=1; i<=n; i++) {
s = br.readLine().split(" ");
w[i] = Integer.parseInt(s[0]);
v[i] = Integer.parseInt(s[1]);
}
System.out.println(knapsack());
}
static int knapsack() {
for(int i=1; i<n+1; i++) {
for(int j=1; j<k+1; j++) {
if(w[i] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
return dp[n][k];
}
}
์ฑ๊ณต~