백준 12865번 - 평범한 배낭(Node.js)

백준 12865번 - 평범한 배낭(Node.js)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

 

---

첫 번째 나의 풀이

	const readline = require("readline");
	const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
	});
	let input = [];
	rl.on("line", function (line) {
	input.push(line);
	N = Number(input[0].split(" ")[0]);
	K = Number(input[0].split(" ")[1]);
	if (input.length - 1 === N) {
	rl.close();
	}
	}).on("close", function () {
	let arr = [];
	let worthArr = [];
	let answer = 0;
	for (let i = 1; i <= N; i++) {
	arr[i - 1] = input[i].split(" ").map((el) => {
	return Number(el);
	});
	}
	for (let i = 0; i < N; i++) {
	for (let j = 0; j < N; j++) {
	if (i !== j) {
	if (arr[i][0] <= K) {
	worthArr.push(arr[i][1]);
	if (arr[i][0] + arr[j][0] <= K) {
	worthArr.push(arr[i][1] + arr[j][1]);
	} else {
	continue;
	}
	}
	}
	}
	}
	answer = Math.max(...worthArr);
	console.log(answer);
	process.exit();
	});

view raw 12865.js hosted with ❤ by GitHub

• 제출시 결과는 틀렸습니다.
• 간단하게 이 코드에 대해 설명하자면, 이중 for문을 사용하여 모든 가치 or 가치의 합의 최댓값의 경우의 수를 worthArr이라는 배열에 넣어주고, worthArr의 값 중 최댓값을 답으로 설정하여 풀었다.
• 하지만, 이 방법에는 생각해보니 많은 오류가 있었다.
• 이중 for문을 사용했기 때문에, 최대 2개의 가치의 합만 계산하기 때문이다. 물론 문제의 입력 예제에는 2개의 가치의 합까지만 고려하도록 나와있지만, 입력의 수가 많고 고려해야할 가치의 갯수가 3개 이상이라면, 이 방법으로는 당연히 풀 수 없다.

 

 

---

두 번째 나의 풀이

• 제가 두 번째의 방법을 알았을 때는 처음에 이해가 가지 않아, 이해하는데 상당한 시간이 걸렸습니다..
• 이 문제는 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)라는 동적 프로그래밍 방법을 사용해야 풀 수 있습니다.
• 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)을 잘 모르시는 분들이라면, 아래의 링크를 클릭해서 이해하셔야 아래 코드를 이해할 수 있을 것 같습니다. 😂😂😂 

2022.07.27 - [Algorithm] - 물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)

물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)

 

	const readline = require("readline");
	const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
	});
	let input = [];
	rl.on("line", function (line) {
	input.push(line);
	N = Number(input[0].split(" ")[0]);
	K = Number(input[0].split(" ")[1]);
	if (input.length - 1 === N) {
	rl.close();
	}
	}).on("close", function () {
	let dp = Array.from(new Array(N + 1), () => Array(K + 1).fill(0));
	let arr = [];
	for (let i = 1; i <= N; i++) {
	arr[i - 1] = input[i].split(" ").map((el) => {
	return Number(el);
	});
	}
	for (let i = 1; i <= N; i++) {
	for (let j = 1; j <= K; j++) {
	if (j - arr[i - 1][0] >= 0) {
	dp[i][j] = Math.max(
	dp[i - 1][j],
	arr[i - 1][1] + dp[i - 1][j - arr[i - 1][0]]
	);
	} else {
	dp[i][j] = dp[i - 1][j];
	}
	}
	}
	console.log(dp[N][K]);
	process.exit();
	});

view raw 12865.js hosted with ❤ by GitHub