배낭에 짐싸기

public class Practice3 {

    public static int solution(int[][] items, int n, int k) {

        int[][] dp = new int[n+1][k+1];
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 1; j <= k; j++){//무게가 충족될떄 까지
                if(items[i][0] > j){// 무게 총량이 넘어간 경우
                    dp[i+1][j] = dp[i][j];// 그전 무게로 전부 채워줌
                }else{
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j-items[i][0]] + items[i][1]);
                }
            }
        }



        return dp[n][k];
    }

    public static void main(String[] args) {
        // Test code
        int[][] items = {{6, 13}, {4, 8}, {3, 6}, {5, 12}};
        System.out.println(solution(items, 4, 7));  // 14
    }
}