[BAE/<JOON> 문제풀이] 12865. 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제 문구를 잘 읽자. 배낭에 넣을 수 있는 물건은 하나까지다.

 

첫 제출하고 계속 틀려서 정답을 보니 하나까지만 넣을 수 있는 문제였다.

 

능 지

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

using namespace std;

struct th {
	int w;
	int c;
};

bool acs(th a, th b) {
	return a.w < b.w;
}

int main()
{
	vector<vector<int>> dp;
	vector<th> arr;
	int n, m;
	cin >> n >> m;

	dp.resize(n + 1);
	arr.resize(n + 1);
	dp[0].resize(m + 1);
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		arr[i] = { a, b };
		dp[i].resize(m + 1);
	}

	sort(arr.begin(), arr.end(), acs);

	for (int j = 1; j <= n; j++) {
		for (int i = 0; i < arr[j].w; i++) {
			dp[j][i] = dp[j - 1][i];
		}
		for (int i = arr[j].w; i <= m; i++) {
			int value = dp[j - 1][i] > dp[j - 1][i - arr[j].w] + arr[j].c ?
				dp[j - 1][i] : dp[j - 1][i - arr[j].w] + arr[j].c;
			dp[j][i] = value;
		}
	}

	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= m; i++) {
			cout << dp[j][i] << " ";
		}
		cout << "\n";
	}

	cout << dp[n][m] << endl;

	return 0;
}