SWEA 3282 0/1 Knapsack

1 개요

SWEA 3282 0/1 Knapsack

SW Expert 아카데미

#	문제	풀이

3 Java

import java.util.*;
public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			int[] V = new int[N];
			int[] C = new int[N];
			for(int i=0; i<N; i++) {
				V[i] = sc.nextInt();
				C[i] = sc.nextInt();
			}
			int a[][] = new int[N+1][K+1];
			for(int i=0; i<=N; i++) {
				for(int w=0; w<=K; w++) {
					if(i==0 || w==0) {
						a[i][w] = 0;
						continue;
					}
					if (V[i-1] <= w) {
						a[i][w] = Math.max(C[i-1]+a[i-1][w-V[i-1]],  a[i-1][w]);
						continue;
					}
					a[i][w] = a[i-1][w]; 
				}
			}
			System.out.format("#%d %d\n", tc, a[N][K]);
		}
		sc.close();
	}
}

4 같이 보기

• 0-1 배낭 문제