평범한 배낭

15 August 2019

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

이번은 대표적인 DP 문제 중 하나인 "냅색 문제"를 풀어보도록 하겠습니다.

#include<stdio.h>

#define max(a,b) (((a)>(b))?(a):(b))

int main(void) {

	int N, K;

	scanf("%d %d", &N, &K);

	int* weight = new int[N];
	int* value = new int[N];
	int** dp = new int*[N];
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &weight[i], &value[i]);
		dp[i] = new int[K + 1];
		for (int m = 0; m < K + 1; m++)
		{
			if (i == 0)
			{
				dp[i][m] = 0;
			}
			else {
				dp[i][m] = dp[i - 1][m];
			}

			if (weight[i] <= m)
			{
				if (i == 0)
				{
					dp[i][m] = value[i];
				}
				else {
					dp[i][m] = max(dp[i][m], dp[i - 1][m - weight[i]] + value[i]);
				}

			}
		}
	}

	printf("%d", dp[N - 1][K]);

	return 0;
}

주어진 무게로 최대의 가치를 갖는 값을 찾아내는 문제입니다.
만약에 A,B,C가 있다고 하면 이중에서 최대값을 찾는 방법은 A가 포함되는 최대값, A가 포함되지 않는 최대값 둘 중에 하나로 볼 수 있습니다.
해당 값을 수식으로 표현하면, max(최대무게) = max(B,C로 이루어진(최대무게)값, A의 가치 + B,C로 이루어진 (최대무게 - A의 무게)) 로 표현할 수 있습니다.
해당 값을 구현 후, return해주도록 합니다.