[SWEA] 3282. 0/1 Knapsack(DP).java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr&categoryId=AWBJAVpqrzQDFAWr&categoryType=CODE

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

Knapsack 문제이지만,

최대 N은 100 이므로 일반 Knapsack 문제로 생각해버리면 

2^100 이 되어버리므로 풀 수 없는 문제이다.

DP를 사용해서 풀어야만 한다.

참고 게시물

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution3282 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 물건 개수
            int W = Integer.parseInt(st.nextToken()); // 가방 부피
            int[][] dp = new int[N + 1][W + 1];
            Item[] bag = new Item[N+1];
 
            for (int i = 1; i <= N; i++) {
                st = new StringTokenizer(br.readLine());
                bag[i] = new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                
                for (int j = 1; j <= W; j++) {
                    // i번째 물건의 무게가 가방 부피보다 크다면
                    if(bag[i].weight > j) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-bag[i].weight] + bag[i].value);
                }
            }
 
            System.out.println("#" + tc + " " + dp[N][W]);
        }
    }
 
}
 
class Item {
    int weight;
    int value;
 
    public Item(int weight, int value) {
        super();
        this.weight = weight;
        this.value = value;
    }
 
}

#. Code_v2

아이템을 저장하는 2차원 배열과

DP 정보를 저장하는 2차원 배열은

N 이 커지면 상당한 메모리 손해를 보게 된다.

아이템은 입력받는 동시에 처리해주고

DP 를 1차원 배열로 사용한다면

메모리 절약을 할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution3282_v2 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 물건 개수
            int W = Integer.parseInt(st.nextToken()); // 가방 부피
            int[] dp = new int[W + 1];
 
            for (int i = 1; i <= N; i++) {
                st = new StringTokenizer(br.readLine());
 
                int weight = Integer.parseInt(st.nextToken());
                int value = Integer.parseInt(st.nextToken());
 
                for (int j = W; j >= weight; j--) {
                    dp[j] = Math.max(dp[j], dp[j - weight] + value);
                }
 
            }
 
            System.out.println("#" + tc + " " + dp[W]);
        }
    }
 
}