12865번 평범한 배낭

문제링크 : www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

 

---

<알고리즘>

  1) 물건들의 무게와, 가치를 입력받은 후, 무게기준 오름차순으로 정렬

  2) 무게당 넣을 수 있는 최대가치 계산을 위한 이차배열 dq를 생성

  3) dq의 열은 0~K까지로 고려하는 무게, 행은 0~N까지로 고려의 대상이 되는 물건의 개수를 의미함

  4) dq의 행=0인 경우 => 고려대상이 되는 물건의 개수가 0,  열=0인경우 => 가방에 담을 수 있는 무게가 0 이므로 dq의 행이나 열이 0인 경우는 가치도 0이다.

  5) dq채우기

    5-1) 지금 고려하는 물건의 무게가 내가 고려하는 칸의 무게보다 작으면, (1)과(2) 중 큰값고르기

          (1) 그 물건의 가치 + (내가고려하는 칸의 무게-그 물건의 무게)가방의 최대가치

          (2) 그 물건을 넣지 않았을 때의 가치

    5-2) 지금 고려하는 물건의 무게가 내가 고려하는 칸의 무게보다 크면, 그 물건을 넣지 않았을 때의 가치 채택

 6) dq[K][N]은 최대 N개의 물건까지 고려하고 최대 K무게 까지 고려했을때 가방에 담을 수 있는 최대 가치이므로 dq[N][K] 출력

 

 

 

 

메모리 : 42004KB   시간 : 52ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	int K = 0;
	cin >> N >> K;
	
	vector<vector<int>> wv(N,vector<int>(2));
	int v = 0;
	int w = 0;
	for (int i = 0; i < N; i++) {
		cin >> w >> v;
		wv[i][0] = w;
		wv[i][1] = v;
	}
	sort(wv.begin(), wv.end());

	vector<vector<int>> dq(N + 1, vector<int>(K + 1));
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			if (i == 0 || j == 0) {
				dq[i][j] = 0;
			}
			else if (wv[i - 1][0] <= j) {
				dq[i][j] = max((wv[i - 1][1] + dq[i - 1][j - wv[i - 1][0]]), (dq[i - 1][j]));
			}
			else {
				dq[i][j] = dq[i - 1][j];
			}
		}
	}
	
	cout << dq[N][K];
	return 0;
}

 

 

 

+) 참고 : ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

배낭 문제 - 위키백과, 우리 모두의 백과사전

+) 참고 : gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)