냅색 문제

첫 코드

DFS로 완전탐색을 했는데 시간이 초과되었다.

#include <bits/stdc++.h>
using namespace std;

int n, m, res=INT_MIN;
vector<pair<int, int> > v;

void DFS(int value, int weight){
	if(weight > m) return;
	else{
		res = max(res, value);
		for(int i=0; i<v.size();i++){
			DFS(value + v[i].second, weight+v[i].first);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a,b));
	}
	
	DFS(0, 0);
	
	cout << res;
}

 

DP 이용

 

#include <bits/stdc++.h>
using namespace std;

int n, m, bag[1001], res;
vector<pair<int, int > > v;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a,b));	
	}

	for(int i=0; i<v.size(); i++){
		for(int j=0; j<=m; j++){
			if(j-v[i].first>=0){
				bag[j] = max(bag[j-v[i].first] + v[i].second, bag[j]);
			}
		}
	}

	for(int i=0; i<=m; i++){
		res = max(res, bag[i]);
	}
	cout << res;

}

 

더 간단한 코드

 

#include <bits/stdc++.h>
using namespace std;

int n, m, bag[1001];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

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

		for(int j=w; j<=m; j++){
			bag[j] = max(bag[j-w] + v, bag[j]);
		}
	}
	cout << bag[m];

}

냅색 알고리즘은

 

무게를 0부터 n까지 돌 때

 

각 요소마다 가방에 넣었을 때 최댓값이 된다면 갱신해주면 된다.