[문제 링크](https://www.acmicpc.net/problem/12865)

1. Bottom-up 방식으로 각 무게에서 최대 가치를 누적해갔다.

- 시간복잡도 : N

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class 평범한배낭 {

static int N, K;

static int dp[][], w[], v[];

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

dp = new int[N + 1][K + 1];

w = new int[N + 1];

v = new int[N + 1];

for (int i = 1; i <= N; i++) {

st = new StringTokenizer(br.readLine());

w[i] = Integer.parseInt(st.nextToken());

v[i] = Integer.parseInt(st.nextToken());

}

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= K; j++) {

dp[i][j] = dp[i - 1][j];

if (j - w[i] >= 0)

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

}

}

System.out.println(dp[N][K]);

}

}

- 착실하게 문제의 요구사항을 따라가면 되는 문제였습니다.