반응형
첫 코드
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까지 돌 때
각 요소마다 가방에 넣었을 때 최댓값이 된다면 갱신해주면 된다.
반응형
'Algorithm > etc' 카테고리의 다른 글
| 플로이드 워샬 알고리즘이란? (냅색 응용) -모든 정점의 최단 거리 구하기 (0) | 2022.01.28 |
|---|---|
| 냅색 알고리즘(한번 만 사용가능) 2차원, 1차원 배열 (0) | 2022.01.26 |
| LIS 최대 부분 증가수열 - DP (0) | 2022.01.25 |
| 랜선자르기, 재귀, 메모이제이션 (0) | 2022.01.24 |
| 라이언 킹 심바 BFS 문제 (0) | 2022.01.24 |