Algorithm
[BOJ] 12865번 : 평범한 배낭
rudgh99_algo
2024. 9. 6. 21:26
1. problem :
https://www.acmicpc.net/problem/12865
2. solution 1 :
#include <bits/stdc++.h>
using namespace std;
int n, k;
int w[100005], v[100005];
int d[100005]; // 무게에따른 최대 value값 저장
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
for (int m = k; m >= w[i]; m--) {
d[m] = max(d[m], d[m - w[i]] + v[i]);
}
}
cout << *max_element(d, d + k + 1) << '\n';
}
1. 무게에 따른 최대 value값을 저장하는 table을 정의한다.
2. 점화식을 정의한다. d [w] = max(d [w], d [w-weight [i]] + value [i])로 구한다. ( 이때, for loop에서 역순으로 시행하는 이유는 정방향으로 시행했을 때는, 중복으로 더해지는 문제가 발생한다.)
3. 초기값을 설정한다. 여기서는 다 0으로 초기화하면 된다.