배낭채우기2(1078) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=561&sca=3050 DP

배낭채우기2(1078).cc

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

using namespace std;

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

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(2, vector<int>(W + 1, 0));
	bool ind = true;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < w[i]; j++)
			d[ind][j] = d[!ind][j];
		for (int j = w[i]; j <= W; j++)
			d[ind][j] = max(d[!ind][j], d[!ind][j - w[i]] + v[i]);
		ind = !ind;
	}
	cout << d[!ind][W];
	return 0;
}