Algorithm/etc
냅색 알고리즘(한번 만 사용가능) 2차원, 1차원 배열
DingCoDing
2022. 1. 26. 23:21
반응형
2차원
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dy[101][1020];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n ;i++){
int point, time;
cin >> point >> time;
for(int j = time; j<=m; j++){
dy[i][j] = max(dy[i-1][j-time] + point, dy[i-1][j]);
}
}
cout << dy[m];
}
1차원
for문을 뒤에서부터 돌면 해결된다
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dy[1020];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n ;i++){
int point, time;
cin >> point >> time;
for(int j = m; j>=time; j--){
dy[j] = max(dy[j-time] + point, dy[j]);
}
}
cout << dy[m];
}
반응형