백준 알고리즘 12865번 - 평범한 배낭 [C]

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

12865번: 평범한 배낭

무식하게 브루트 포스로 풀려다가 못 풀고 낑낑댔다..

 

정말 나는 아무것도 모르는 감자라는 걸 다시 느꼈다.

 

DP라고 동적 계획법이라는 프로그래밍 기법으로 풀어야하는 문제라고 하더라

 

Knapsack 알고리즘이라는 것이 있는데,, 어느 블로그를 가든 코드가 하나같이 다 똑같다.

 

정형화된 알고리즘인가 보다.

 

---

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int i, j, n, k;
	int *warr, *varr, *arr;

	scanf("%d %d", &n, &k);


	warr = (int *)malloc(sizeof(int) * n);
	varr = (int *)malloc(sizeof(int) * n);
	arr = (int *)malloc(sizeof(int) * (k+1));

	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &warr[i], &varr[i]);
		if (varr[i] == 0)
			warr[i] = 0;
	}

	for (i = 0; i < k; i++)
		arr[i] = 0;

	for (i = 0; i < n; i++)
	{
		for (j = k; j > 0; j--)
		{
			if (warr[i] <= j)
			{
				if (arr[j] < arr[j - warr[i]] + varr[i])
					arr[j] = arr[j - warr[i]] + varr[i];
			}
		}
	}

	printf("%d", arr[k]);

	free(warr);
	free(varr);
	free(arr);

	return 0;
}

 

여기 저기 찾아보다 가장 잘 설명해준 블로그가 있어 거기 링크를 보는게 좋을 것 같다.

 

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

 

---

무식하게 브루트 포스로 써본 코드는 아래와 같다.

 

백준에 채점하면 시간 초과로 실패한다

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int max = 0;

void find(int n, int k, int *warr, int *varr, int index, int w, int v)
{
	int i;

	if (index == n)
		return;

	else
	{
		
		if (w + warr[index] <= k)
		{
			w += warr[index];
			v += varr[index];

			if (v > max)
				max = v;

			for (i = 1; index + i < n; i++)
				find(n, k, warr, varr, index + i, w, v);
		}
		else
			return;
	}
}


int main(void)
{
	int i, j, n, k, w, v;
	int *warr, *varr;

	scanf("%d %d", &n, &k);

	warr = (int *)malloc(sizeof(int) * n);
	varr = (int *)malloc(sizeof(int) * n);

	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &warr[i], &varr[i]);
		if (varr[i] == 0)
			warr[i] = 0;
	}

	
	for(i=0; i<n; i++)
		find(n, k, warr, varr, i, 0, 0);

	printf("%d", max);


	free(warr);
	free(varr);

	return 0;
}

 

재귀 함수를 써서

 

모든 경우의 수를 전부 다 더해보고, 가장 큰 값을 출력하는 코드이다..

 

시간 복잡도가 n^3 정도 되려나 싶다..

 

정말 갈 길이 멀구나..