메모

/*
N 개 = 여행에 필요한 물건 개수 (1 ≤ N ≤ 100)
W = 각 물건의 무게 (1 ≤ W ≤ 100,000)
V = 가치, 즐거움 (0 ≤ V ≤ 1,000)
K = 최대 가능한 무게 (1 ≤ K ≤ 100,000)

배낭에 넣을 수 있는 물건들의 가치합(V)의 최댓값?
*/

---

해결법

• 배낭 문제

  • 짐을 쪼갤 수 있는 경우

    • "Fraction Knapsack Problem"
    • 그리디 알고리즘으로 해결

  • 짐을 쪼갤 수 없는 경우

    • "0/1 Knapsack Problem"
    • DP(다이나믹 프로그래밍)로 해결 -> 이 문제의 경우 풀이법

• 2차원 배열 dp[][]

  • dp[아이템 index][무게] = 가치
    

방법 1

import java.io.*;
import java.util.*;
 
public class Main {
    static int N,K;
    static int dp[][], w[], v[];
    public static void main(String[] args) throws Exception{
    
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();		// 물건 개수
        K = sc.nextInt();		// 최대 가능 무게
        
        dp = new int[N+1][K+1];
        w = new int[N+1];		// 무게
        v = new int[N+1];		// 가치
        
        for (int i = 0; i < N; i++) {
            w[i]= sc.nextInt();
            v[i] = sc.nextInt();
        }
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                dp[i][j] = dp[i-1][j];     // 이전 행의 결과값 복사 (item 2에서부터)
                
                if (j - w[i] >= 0) {    // 무게가 남을 경우 (최대 가능 무게 - 무게)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]]+v[i]);		// 더 큰 값으로 갱신
                }
            }
        }
        
        System.out.println(dp[N][K]);
    }
}

---

참고: [백준] 12865번 평범한 배낭 (자바 풀이)

---

평범한 배낭 (백준 12865번)