[백준 / C언어] 12865번: 평범한 배낭

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

12865번: 평범한 배낭

 

Knapsack Problem으로 유명한 문제다

 

이 알고리즘에 대해 설명해보려고 했는데 너무 길어지고 글로 설명 못하겠어서 포기했다...ㅠ

 

대신 내가 참고했던 유튜브의 링크를 첨부할 테니 이 알고리즘에 대해 이해가 되지 않는 분이 본다면 분명 도움이 될 것이다

 

https://youtu.be/nLmhmB6NzcM

https://youtu.be/rhda6lR5kyQ

 

내가 작성한 코드를 설명해 보겠다

 

배열 arr는 가방이 버틸 수 있는 최대 무게가 열의 index만큼 일 때 최대로 가질 수 있는 value를 나타내고

 

배열 prev는 위의 유튜브에서 나타낸 2차원 배열을 1차원으로 나타내기 위해 이전에 채운 배열 arr의 값을 복사하는 용도로 사용했다

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a,b) ((a)>(b)?(a):(b))

int main() {
	int N, K, i, j;
	scanf("%d %d", &N, &K);

	int* arr = (int*)calloc(K + 1, sizeof(int));
	int* prev = (int*)calloc(K + 1, sizeof(int));
	int* weight = (int*)calloc(N, sizeof(int));
	int* value = (int*)calloc(N, sizeof(int));

	for (i = 0; i < N; i++) {
		scanf("%d %d", &weight[i], &value[i]);
	}

	int prev_weight;
	for (i = 0; i < N; i++) {
		for (j = 1; j <= K; j++) {
			prev_weight = j - weight[i];	// 물건을 담기 전의 무게
			if (prev_weight < 0)	// 물건을 담을 수 없을 때
				arr[j] = prev[j];
			else
				arr[j] = max(prev[j], prev[prev_weight] + value[i]);
		}
		/* prev에 현재 행의 값 저장 */
		for (j = 1; j <= K; j++)
			prev[j] = arr[j];
	}
	printf("%d", arr[K]);
	free(arr);
	free(prev);
	free(weight);
	free(value);
	return 0;
}