평범한 배낭 - 12865번

---

풀이 방법

이번 다이나믹 프로그래밍 문제에선 배낭안에 물건이 한번씩만 들어간다는 것이 중요한 조건이였다.

순서대로 넣어서 최댓값을 찾으려고 하니 중복으로 들어가게 되었다.

반복문을 반대로 돌려서 한번씩만 들어가도록 했다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] d = new int[K + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());

            for (int j = K; j >= W; j--) {
                d[j] = Math.max(d[j], d[j - W] + V);
            }
        }

        System.out.println(d[K]);

    }
}