평범한 배낭 - 12865 ( 미완성 )

문제

풀이

DFS 시도

import java.util.*;

// 평범한 배낭 - DP문제 - G5
class Bag {
    int w; // 무게
    int v; // 가치
    public Bag(int w, int v) {
        this.w = w;
        this.v = v;
    }
}
public class ex12865 {
    static int n; // 물건의 개수
    static int k;  // 최대 무게
    static ArrayList<Bag> arr;
    static int answer=Integer.MIN_VALUE;
    static boolean[] ch;
    public static void DFS(int w,int sum){
        if(w<=k) answer = Math.max(answer,sum);
        if(w>k) return;
        else{
            for(int i=0; i<arr.size(); i++){
                if(!ch[i]){
                    ch[i]=true;
                    DFS(w+arr.get(i).w,sum+arr.get(i).v);
                    ch[i]=false;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        arr = new ArrayList<>();
        ch = new boolean[n];
        for(int i=0; i<n; i++){
            int a = sc.nextInt();
            int b=  sc.nextInt();
            arr.add(new Bag(a,b));
        }
        DFS(0,0);
        System.out.println(answer);
    }
}

결과는 제대로 나오나 , 시간초과로 인한 런타임에러!
이럴 경우엔 --> 무조건 DP 확정
주어지는 값들의 범위가 100단위가 넘어가면 DFS는 재귀호출방식이라서 효율이안좋다. 이런 경우들에는 DP로 해결해보자.

DP 시도

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 평범한 배낭 - DP문제 - G5

public class ex12865 {
    static int n; // 물건의 개수
    static int k;  // 최대 무게
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        int[] w = new int[n+1];
        int[] v = new int[n+1];
        int[] dp = new int[k+1];

        for(int i=1; i<=n; i++){
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            for(int j=k; j-w[i]>=0; j--){
                dp[j]=Math.max( dp[j] , dp[j-w[i]] + v[i]);
            }
        }
        System.out.println(dp[k]);
    }
}