냅색 알고리즘(한번 만 사용가능) 2차원, 1차원 배열

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];
	

}