[c++] 가방문제(냅색 알고리즘)

// 내가 푼 코드
#include<bits/stdc++.h>
using namespace std;

int a[31][31];
int dy[1001];
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, l, w, v;
	cin >> n >> l;
	for(int i=0; i<n; i++){
		cin >> w >> v;
		a[i][0] = w;
		a[i][1] = v;
	}
	
	for(int i=0; i<n; i++){
		for(int j=a[i][0]; j<=l; j++){
			if(dy[j]<dy[j-a[i][0]]+a[i][1]){
				dy[j]=dy[j-a[i][0]]+a[i][1];
			}
		}
	}
	cout<< dy[l];
	return 0;
}

// 강의코드
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, l, w, v;
	cin >> n >> l;
	vector<int> dy(l+1, 0);
	for(int i=0; i<n; i++){
		cin >> w >> v;
		for(int j=w; j<=l; j++){
			dy[j] = max(dy[j], dy[j-w]+v);
		}
	}
	cout<< dy[l];
	return 0;
}

냅색 알고리즘이 사용된 문제로 dynamic programming 을 사용해서 풀 수 있다.

냅색 알고리즘은 가방과 용량이 주어지고 가방에 넣을 물건들과 각각의 물건의 가치가 주어지면

가방에 물건들을 넣어 최대한의 가치를 만들어내는 것을 목표로 한다.

입력이 아래와 같을 때

4 11

5 12

3 8

6 14

4 8

첫줄에 물건과 가방에 대한 정보가 나타난다. 4개의 물건이 주어지고 가방의 용량은 11이다.

다음줄부터 물건의 무게와 그 물건의 가치가 나타난다. 

첫번째 물건의 무게는 5이며 12만큼의 가치를 가지고 있다.

두번째 물건의 무게는 3이며 8만큼의 가치를 가지고 있다. 

이렇게 4번째 물건의 정보까지 입력 받는다.

 

dynamic 배열은 가방의 용량이 1부터 l까지의 경우를 다 고려하기 위해 l만큼의 크기로 잡는다.

이렇게 배열을 잡아놓고

1. 첫번째 물건(무게:5, 가치: 12)을 담는다고 가정

가방의 용량이 1부터 4까지라면 첫번째 물건을 담지 못한다. 가방의 용량이 5부터는 담을 수 있으므로 

담을 수 있는 순간부터 기존에 있는 가치보다 더 높은 가치를 가지면 그 값으로 변경해준다.

 

2. 두번째 물건(무게:3 가치: 8)을 담는다고 가정

가방의 용량이 1부터 3까지라면 두번째 물건을 담지 못한다. 가방의 용량이 3부터는 담을 수 있으므로 

그 순간부터 기존 가치보다 더 높은 가치를 가지는 경우 그 값으로 변경한다.

이렇게 용량이 6까지 오면 기존 값인 dy[6]과 dy[6-3]+v의 값을 비교하여 더 큰 값을 dy[6]에 넣어준다.

이런 방식으로 dy배열을 채워나가면 dy배열의 해당 인덱스에 들어가는 값은 그 용량에서 가장 큰 가치를 가지게 된다.

 

이러한 방식으로 계속 dy를 채워나가면 마지막인덱스에서는 최대의 가치를 찾아낼 수 있다.