[C++] 백준 12865 평범한 배낭

문제 링크

---

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

 

접근 방법

---

 

이 문제는 knapsack 알고리즘의 가장 기본적인 문제이다.

 

(1) 변수

    dp[i]는 배낭의 가용한 최대 무게가 i일때 담을 수 있는 최대의 가치를 의미한다.

    tmp[i]는dp[i]를 갱신하기 전에 미리 복사를 해놓는 용도로 사용. (dp[i]는 실시간으로 갱신 되기 때문에 갱신된 값이 사용되는 것을 방지하고, dp를 2차원으로 사용하는 것보다 시간적 메모리적 효율이 좋다.) 

 

(2) solve() 함수

if (item[i].first <= j) {
	dp[j] = max(tmp[j], tmp[j - item[i].first] + item[i].second);
}

    가장 핵심이 되는 부분인데, max()안에서 tmp[j]는 현제 가리키고 있는 물건 item[i]를 담지 않았을 때의 경우이고,

tmp[j - item[i].first] + item[i].second는 item[i]를 담는 경우, item[i]의 무게를 제외한 부분의 가용한 무게에서의 가치의 최댓값 tmp[j - item[i].first]에 현재 item[i]의 가치를 담는 것이다. 그 둘의 값중 더 큰 가치를 가지는 것으로 dp[j]를

갱신하면 된다.

    

소스 코드

---

#include <vector>
#include <algorithm>

using namespace std;
pair <int, int> item[101];
int dp[100001]; 
int tmp[100001];
int n, k;

int solve() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			tmp[j] = dp[j];
		}
		for (int j = 1; j <= k; j++) {
			if (item[i].first <= j) {
				dp[j] = max(tmp[j], tmp[j - item[i].first] + item[i].second);
			}
		}
	}
	return dp[k];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int w, v;
		cin >> w >> v;
		item[i] = { w,v }; //{무게, 가치}
	}
	cout << solve();
}

개발 환경 : VS 2019

질문, 지적 환영입니다.