Baekjoon - 12865

문제

Solved.ac Class4

1,2 차시도

public class Main {
	private static Data[] data;
	private static int value = -1;
	private static int itemCount;
	private static int weightLimit;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		itemCount = Integer.parseInt(split[0]);
		weightLimit = Integer.parseInt(split[1]);

		data = new Data[itemCount];

		for (int i = 0; i < itemCount; i++) {
			split = br.readLine().split(" ");
			data[i] = new Data(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
		}

		Arrays.sort(data, Comparator.reverseOrder());

		for (int i = 0; i < itemCount; i++) {
			int solve = solve(i, 0, 0);
			value = Math.max(value, solve);
		}

		System.out.println(value);

	}

	private static int solve(int start, int weightSum,int valueSum) {
		if (weightLimit == weightSum) {
			return valueSum;
		}
		int sum = valueSum;

		for (int i = start; i < itemCount; i++) {
			if (data[i].weight + weightSum <= weightLimit) {
				int solve = solve(i + 1, data[i].weight + weightSum, valueSum + data[i].value);
				sum = Math.max(solve, sum);
			}
		}
		return sum;
	}

	static class Data implements Comparable<Data>{
		int weight;
		int value;

		public Data(int weight, int value) {
			this.weight = weight;
			this.value = value;
		}

		@Override
		public int compareTo(Data o) {
			return weight - o.weight;
		}
	}

}

시간초과

Knsapsack 알고리즘

배낭문제를 풀 때 사용하는 알고리즘이다
지금까지는 1차원 배열에 데이터를 넣어서 DP계산을 했다면
2차원 배열에 가로 세로로 데이터를 만들어서 DP계산을 하면 완성이다

각각의 요소(아이템) 을 따라 간다.
기본값은 같은 무게, 위에값으로 하며 현재 들려는 무게 - 아이템무게 가 음수면 더 들수 없고, 0이면 현재 아이템만 들수 있고, 0이상이면 더 들수 있다는 말이므로 맞춰서 해결해주면 된다

3차시도

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int itemCount = Integer.parseInt(split[0]);
		int weightLimit = Integer.parseInt(split[1]);

		int[] weight = new int[itemCount + 1];
		int[] value = new int[itemCount + 1];
		int[][] dp = new int[itemCount + 1][weightLimit + 1];

		for (int i = 1; i < itemCount + 1; i++) {
			split = br.readLine().split(" ");

			weight[i] = Integer.parseInt(split[0]);
			value[i] = Integer.parseInt(split[1]);
		}

		for (int i = 1; i < itemCount + 1; i++) {
			for (int j = 1; j < weightLimit + 1; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - weight[i] >= 0) {
					dp[i][j] = Math.max(dp[i][j], dp[i-1][j-weight[i]]+value[i]);
				}
			}
		}

		System.out.println(dp[itemCount][weightLimit]);

	}
}