💡 다이나믹 프로그래밍/배낭 문제
Memory 41476KB Time 48ms Code Length 754B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;
int n, k; // 물품의 수와 최대 무게제한
int w[101] = {0,}; // 무게
int v[101] = {0,}; // 가치
int dp[101][100001]; // index 와 무게제한
void init() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
}
void make_dp_table() {
for (int lim = 1; lim <= k; lim++) {
for (int idx = 1; idx <= n; idx++) {
if (lim < w[idx]) { // 무게 제한을 넘는 물건 이라면
dp[idx][lim] = dp[idx - 1][lim];
}
else {
dp[idx][lim] = max(dp[idx - 1][lim], dp[idx - 1][lim - w[idx]] + v[idx]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
init();
make_dp_table();
cout << dp[n][k] << endl;
}
이 코드는 배낭 문제를 해결하는 알고리즘을 구현한 것이다. init 함수에서는 물품의 수와 최대 무게제한을 입력받고, 각 물품의 무게와 가치를 배열에 저장한다. make_dp_table 함수에서는 다이나믹 프로그래밍을 이용하여 최대 가치를 계산하는 dp 테이블을 만든다. 이때, 물건을 넣을 수 있는 경우와 넣을 수 없는 경우를 고려하여 dp 테이블을 채워나간다. 마지막으로 main 함수에서는 입력을 받고 dp 테이블을 만들어 최종적으로 얻을 수 있는 최대 가치를 출력한다.
