백준 - 12865 배낭 문제

무게를 인덱스로 활용 할 수 있어야한다.

바텀업을 사용한다면 i,j 를 1부터 사용할 수 있다는 생각을 해야한다. 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

vector<vector<int>> dp(101, vector<int>(100001, 0));

int Dp(vector<pair<int, int>>& thing, int n, int k)
{
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			int currentW = thing[i].first;
			int currentV = thing[i].second;

			if (currentW <= j)
			{
				// 
				dp[i][j] = max(dp[i -1][j], dp[i - 1][j - currentW] + currentV);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}

		}
	}
	return dp[n][k];
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	int n, k;

	cin >> n >> k;

	vector<pair<int, int>> thing(101);

	for (int i = 1; i <= n; ++i)
	{
		int w, v;
		cin >> w >> v;

		thing[i].first = w;
		thing[i].second = v;
	}

	cout << Dp(thing, n, k);

	return 0;
}