0/1 배낭 문제(Knapsack Problem) (3740) : http://codeup.kr/JudgeOnline/problem.php?id=3740 DP

01 배낭 문제(Knapsack Problem) (3740).cc

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

/*
시간 복잡도 : O(NW) ( 물건 개수 * 배낭에 넣을 수 있는 최대 무게 ) 
공간 복잡도 : O(NW) ( 물건 개수 * 배낭에 넣을 수 있는 최대 무게 )
*/

int main()
{
	int N, W;
	cin >> N >> W;
	vector<int> w(N+1);//i번째 물건 무게
	vector<int> v(N+1);//i번째 물건 가격
	for (int i = 1; i <= N; i++)
		cin >> w[i] >> v[i];
	
	//d[i][j] = 물건을 i번째 까지 가방을 넣을 때 
	//			무게 j를 초과하지 않으면서 
	//			담을 수 있는 가격의 총합의 최대값
	vector<vector<int>> d(N + 1, vector<int>(W + 1, 0));
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < w[i]; j++)
			d[i][j] = d[i - 1][j];
		for (int j = w[i]; j <= W; j++)
			d[i][j] = max(d[i - 1][j], d[i - 1][j - w[i]] + v[i]);
	}
	cout << d[N][W];
	return 0;
}