0/1 Knapsack problem

백준 12865

 

#include <iostream>
#include <math.h>
using namespace std;

int arr[101][100001] = { 0 };
int weights[101];
int values[101];

int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 1; i < n+1; i++)
	{
		cin >> weights[i] >> values[i]; // 맨 윗줄은 0으로 채워두고 시작.
	}

	for (int i = 1; i < n + 1; i++) // 맨 윗줄은 0으로 채워두고 시작.
	{
		for (int j = 1; j < k + 1; j++)
		{
			if (j >= weights[i]) {
				arr[i][j] = values[i] + arr[i - 1][j - weights[i]];
			}
			if (arr[i - 1][j] > arr[i][j]){
				arr[i][j] = arr[i - 1][j];
			}
		}
	}

	cout << arr[n][k];

	return 0;
}

참고:

www.youtube.com/watch?v=cJ21moQpofY&t=350s&ab_channel=WilliamFiset