안녕하세요,
재재입니다.
boj 12920 평범한 배낭2 문제에 대한 솔루션입니다.
BOJ 12920 평범한 배낭2
(1) 문제 설명
출처: https://www.acmicpc.net/problem/12920
(100 이하) N 개의 물건과, 배낭에 최대로 넣을 수 있는 무게는 (10000이하) M 입니다.
각 물건은, 가방에 넣었을 때 무게, 만족도 및 개수가 들어옵니다.
최대 무게를 넘기지 않으면서, 최고의 만족도를 구해주면 됩니다.
(2) TLE 코드
bottom-up 방식으로 문제의 솔루션을 내봤는데요.
전형적인 배낭 (knapsack) 문제의 변형 중 하나고,
점화식을 아래와 같이 정할 수 있습니다.
dp[S] : 현재 무게 S 에서 최적의 만족도
$$
dp[S] = dp[P + w_i] + satisfication_i
$$
이때, 시간 복잡도는 다음과 같습니다.
$$
O(NMK)
$$
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[10003];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)dp[i] = -1;
for (int i = 0; i < n; i++) {
int v, c, k;
scanf("%d %d %d", &v, &c, &k);
for (int j = m; j >= 0; j--) {
if (dp[j] != -1) {
for (int l = k; l >= 1; l--) {
if (j + v*l <= m) {
dp[j + v*l] = max(dp[j + v*l], dp[j] + c*l);
}
}
}
}
}
int ans = 0;
for (int i = 0; i <= m; i++)ans = max(ans, dp[i]);
printf("%d\n", ans);
}
(3) 풀이 도출
위의 TLE 코드에서의 시간 복잡도는 이 문제를 풀기에 힘들기 때문에,
획기적인 방법이 필요합니다.
이때, 좀 더 활용 할 수 있는 정보는 바로 객체의 갯수 입니다.
갯수를 6개일 때, 6개를 사용하는 경우의 수를 표현해볼게요.
$$
1 + 1 + 1 + 1 + 1 + 1
= 1 + 2 + 3 = 2 + 4 ?
$$
이번엔, 10개일 때 한번 표현해볼게요.
$$
1 + 1 + 1 … + 1
= 1 + 2 + 4 + 3
$$
뭔가 2진수를 잘 엮으면,
갯수에 대한 정보가 필요가 없어질 수도 있겠다는 생각이 들었습니다.
2진법과 비슷하게 생각해보려니, 시간 복잡도는 갯수의 K 가 아니라,
$$
O(logK)
$$
이 방식을 구현하면 아래와 같습니다.
(4) 정답 코드
BOJ 12920 평범한 배낭2