Knapsack
---
layout: post
title: "Knapsack Algorithm의 여러 응용"
author: knon0501
date: 2023-03-18
tags: [dynamic-programming]
---
Introduction
배낭 문제란 무게제한이 있는 가방에 고유한 무게와 가치를 가지는 물건들을 채워넣을 때 어떻게 해야 최대 가치를 가방에 넣을 수 있을지 계산하는 문제입니다. 무게에 별다른 제한이 없을 경우 물건이 총 $N$개일 때 $O(2^N\times N)$정도의 시간복잡도로 계산할 수 있으며 NP-complete 임이 알려져 있습니다. 물건의 무게가 정수이고 가방의 무게제한이 $W$일 경우 동적계획법으로 $O(NW)$에 해결할 수 있습니다. 이 글에서는 독자가 동적계획법으로 배낭 문제를 해결하는 법을 이미 알고 있다고 전제하고 다양한 배낭문제의 응용들을 살펴보겠습니다.
각 물건을 여러개 사용할 수 있는 경우
BOJ12920 문제를 살펴봅시다. $K$가 최대 10000이기 때문에 일반적인 동적계획법으로는 $O(NMK)$로 시간초과를 받습니다. 때문에 다른 방법을 생각해보아야 합니다.
물건을 묶어서 생각하는 방법
어떤 물건을 최대 100개 쓸 수 있다고 생각해봅시다. 물건을 1개묶음,2개묶음,4개묶음,8개묶음,16개묶음,32개묶음,37개묶음으로 나눈다면 물건 7개만으로 물건이 1개 존재하는 것부터 100개 존재하는 것까지 모두 표현할 수 있습니다. 즉 물건이 $K$개 존재한다면 $2^{t+1}-1< K $를 만족하는 가장 큰 $t$에 대하여 물건을 $2^0$개, $2^1$개, $2^{2}$개,…, $2^{t}$개, $K-2^{t+1}+1$개씩 묶어서 $K$개의 물건을 $O(\log K)$개의 물건으로 치환할 수 있습니다. 따라서 전체 문제가 $O(NM\log K)$에 해결됩니다.
#include <bits/stdc++.h>
using namespace std;
int a[101];
int c[101];
int b[101];
int dp[10001];
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int n,m;
cin>>n>>m;
int i,j,k;
for(i=1 ; i<=n ; i++)cin>>a[i]>>c[i]>>b[i];
for(i=1 ; i<=n ; i++){
int s=b[i];
for(k=0 ; (1<<k)<=s ; k++){
s-=(1<<k);
for(j=m ; j>=(a[i]<<k); j--)
dp[j]=max(dp[j],dp[j-(a[i]<<k)]+(c[i]<<k));
}
for(j=m ; j>=s*a[i] ; j--)
dp[j]=max(dp[j],dp[j-s*a[i]]+c[i]*s);
}
cout<<dp[m];
return 0;
}
DP최적화의 관점에서 생각하는 방법
$DP[i]=$ 무게 합이 $i$ 가 되도록 하는 물건 가치 합의 최댓값 으로 정의합시다. $j$번째 물건의 가치가 $V_j$,무게가 $W_j$이고 개수제한이 $K_j$라고 할 때 점화식은 $DP[i]=\underset{1 \leq k \leq K_j}{\max} DP[i-W_j\times k]+V_j\times k$입니다.
이걸 다르게 써보면 $DP[i]=\underset{i \equiv k \mod{W_j}}{\max}DP[k]+V_j\times(i-k)/W_j$ 입니다. 여기서 $DP2[i]=DP[i]-i\times V_j/W_j$라 하면 $DP2[i]=\underset{i\equiv k \mod{W_j}}{\max}DP2[k]$ 가 되어 구간 최솟값을 구하는 문제로 바뀝니다. 따라서 세그먼트 트리를 이용하는 경우 $O(NM\log M)$, deque를 이용하는 경우 $O(NM)$으로 전체 문제를 해결 가능합니다.
비슷한 방식으로 물건의 무게가 특정한 범위로 주어지는 BOJ14205도 해결 가능합니다. 다음은 BOJ14205를 해결하는 코드입니다.
#include <bits/stdc++.h>
using namespace std;
long long dp[100001];
int a[1001];
int b[1001];
long long p[1001];
void solve(int T){
int N,M,L;
cin>>N>>M>>L;
for(int i=1 ; i<=N ; i++)
cin>>a[i]>>b[i]>>p[i];
for(int i=1 ; i<=L ; i++)
dp[i]=1e18;
for(int i=1 ; i<=N ; i++){
int k=L-a[i];
deque<int> dq;
for(int j=L ; j>=a[i] ; j--){
while(!dq.empty() && dq.front()>j-a[i])
dq.pop_front();
while(k>=j-b[i] && k>=0){
while(!dq.empty() && dp[k]<=dp[dq.back()])
dq.pop_back();
dq.push_back(k);
k--;
}
if(!dq.empty()){
dp[j]=min(dp[j],dp[dq.front()]+p[i]);
}
}
}
cout<<"Case #"<<T<<": ";
if(dp[L]<=M)
cout<<dp[L]<<'\n';
else
cout<<"IMPOSSIBLE\n";
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int T;
cin>>T;
for(int i=1 ; i<=T ; i++)
solve(i);
return 0;
}
가방의 무게 제한이 매우 큰 경우
1. $O(N^2w)$
다음과 같은 문제를 생각해봅시다.
배열 $A,B$가 주어질 때 $A_1x_1+A_2x_2+…+A_Nx_N\leq M$ 일 때 $B_1x_1+B_2x_2+…+B_Nx_N$을 최대화 하여라. $($모두 정수, $A_i\leq w)$
이는 무게가 $A_i$이고 가치가 $B_i$인 물건들이 주어질 때 크기가 $M$인 배낭에 물건을 중복을 허용해서 넣어 최대 가치를 찾는 문제와 동일합니다. $O(NM)$의 동적계획법으로 풀 수 있지만 $M$이 10억정도가 되면 곤란합니다. 하지만 $M$이 크더라도 $N$과 $w$가 작은 경우에는 해결 가능합니다.
직관적으로 $B_i/A_i$가 가장 큰 물건을 많이 사용하는 것이 유리합니다. 즉, 효율이 가장 좋은 물건을 배낭에 넣는 것이 좋습니다. 구체적으로, 효율이 가장 좋은 물건들을 제외한 나머지 물건들은 무게의 총합이 $Nw$보다 작게 됩니다. $Nw$보다 무게합이 큰 경우에는 효율이 가장 좋은 물건으로 바꿔치기하는 것이 더 유리하기 때문입니다. 무게합이 $O(Nw)$이하인 경우 최대가치를 동적계획법으로 계산하면 $O(N^2w)$이고 나머지 무게는 효율이 가장 좋은 물건으로 채워넣으면 됩니다.
연습문제로는 BOJ19404가 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long dp[1600005];
int p[1600005];
int m;
int n;
char b[405];
int a[405];
int y[405];
int x;
int main(){
cin>>x;
cin>>b+1;
int n = strlen(b + 1);
if(b[1]!='Y'){
cout<<0<<endl;
cout<<x<<" ";
for(int i=2 ; i<=n ; i++)
cout<<0<<" ";
return 0;
}
for(int i=1 ; i<=n ; i++){
if(b[i]=='Y'){
m++;
a[m]=a[m-1]+1;
}
else a[m]++;
}
for(int j=1 ; j<=n*n ; j++){
dp[j]=1e18;
}
for(int i=1 ; i<=m ; i++){
for(int j=a[i] ; j<=n*n ; j++){
if(dp[j-a[i]]+i<dp[j]){
p[j]=i;
dp[j]=dp[j-a[i]]+i;
}
}
}
int k=1;
for(int i=1 ; i<=m ; i++){
if((double)a[i]/i>(double)a[k]/k){
k=i;
}
}
long long ans=1e18;
int j=0;
int kk=0;
for(int i=0 ; i<=n*n ; i++){
if(ans>dp[i] && i>=x){
kk=0;
j=i;
ans=dp[i];
}
else if(i<x && ans>dp[i]+(long long)(x-i+a[k]-1)/a[k]*k){
j=i;
kk = (x - i + a[k] - 1) / a[k];
ans = dp[i] + (long long)(x - i + a[k] - 1) / a[k] * k;
};
}
y[k]+=kk;
while(j>0){
y[p[j]]++;
j-=a[p[j]];
}
cout<<ans<<endl;
for(int i=m ; i>=1 ; i--){
y[i-1]+=y[i];
}
int s=x;
for(int i=1 ; i<=m ; i++){
for(int j=0 ; j<a[i]-a[i-1] ; j++){
cout<<min(y[i],s)<<" ";
s-=min(y[i],s);
}
}
}
2. $O(w^2\log S)$
문제를 살펴봅시다. 물건은 가방에 여러 번 넣을 수 있으며 가방의 무게 제한 $S$는 $10^9$으로 매우 크고 물건의 종류 $N$과 각 물건의 무게 $w_i$는 $10^3$이하로 작습니다. 가방의 무게제한이 매우 크기 때문에 일반적인 DP로는 당연히 해결할 수 없습니다.
$DP[i]=$무게 합이 $i$가 되도록 물건들을 조합할 때 최대 가치 로 정의합시다. 그러면 다음과 같은 점화식이 성립합니다.
$DP[i]=\underset{0 < j < i}{\max}DP[j]+DP[i-j]$
이것을 그냥 계산하면 $O(S^2)$으로 시간초과를 받습니다. 그런데 여기서 $j$범위를 다음과 같이 바꿀 수 있습니다.
| $DP[i]=\underset{\left | j-(i-j)\right | \leq w}{\max}DP[j]+DP[i-j]$ |
$j$와 $i-j$의 차이가 물건이 가질 수 있는 무게의 최댓값보다 큰 경우는 볼 필요가 없다는 것입니다. 만약 무게 차이가 $w$보다 크다면 무게합이 더 큰 쪽에서 작은 쪽으로 물건을 옮길 수 있기 때문입니다. 따라서 $DP[X-w]…DP[X+w]$의 값을 알고 있다고 할 때 $DP[2X-w]…DP[2X+w]$의 값을 $O(w^2)$에 알 수 있고 배낭의 크기를 두 배씩 늘리면 $O(w^2\log S)$로 전체 문제를 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,long long> dp;
const int D=1000;
unordered_map<int,int> vis;
long long f(int x){
if(vis[x] || x<=2*D)return dp[x];
vis[x]=1;
for(int i=x/2-D/2 ; i<=x/2 ; i++){
dp[x]=max(f(i)+f(x-i),dp[x]);
}
return dp[x];
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int n,m;
cin>>n>>m;
long long mx=0;
long long ans=0;
for(int i=1 ; i<=n ; i++){
int w;
long long c;
cin>>w>>c;
for(int j=w ; j<=D*2 && j<=m; j++){
dp[j]=max(dp[j],dp[j-1]);
dp[j]=max(dp[j],dp[j-w]+c);
ans=max(ans,dp[j]+dp[m-j]);
}
}
cout<<f(m);
return 0;
}
물건의 무게가 작은 경우
BOJ13058를 봅시다. 물건의 개수 $N$이 1000000, 배낭의 크기 $K$가 100000으로 크므로 일반적인 DP로는 해결할 수 없습니다. 하지만 물건의 크기 $s$가 300 이하라는 것을 통해 해결할 수 있습니다.
$C[i][j]=$크기가 $i$인 물건을 $j$개 담을 때 얻을 수 있는 최대 가치 로 정의합시다. 당연히 가치가 높은 물건부터 담는 것이 이득이기 때문에 그리디 기법으로 쉽게 구해놓을 수 있습니다.
$DP[i][j]=$크기가 $i$이하인 물건들만 사용하여 $j$크기만큼 물건들을 담았을 때 최대가치 로 정의합시다. 다음 점화식이 성립합니다.
$DP[i][x+i\times j]=DP[i-1][x+i\times k]+C[i][j-k] $
$C[i][]$은 위로 볼록하므로 Monge Array로 변형할 수 있기 때문에 고정된 $x$에 대하여 divide and conquer 알고리즘을 적용하여 전체 $O(Ks\log K+N)$으로 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<int> a[301];
vector<long long> s[301];
long long dp[301][100001];
int n,m;
void f(int d,int l,int r,int x,int y,int w){
if(l>r)return;
int mid=l+r>>1;
int k=mid*w+d;
int opt;
if(k<=m){
opt=0;
dp[w][k]=dp[w-1][k];
for(int i=x ; i<=y && i<=mid; i++){
int t=(mid-i);
if(t>a[w].size())continue;
long long c=s[w][t];
int j=i*w+d;
if(dp[w][k]<=dp[w-1][j]+c){
dp[w][k]=dp[w-1][j]+c;
opt=i;
}
}
}
else
opt=y;
//cout<<mid<<" "<<w<<" "<<dp[w][mid]<<" "<<opt<<endl;
f(d,l,mid-1,x,opt,w);
f(d,mid+1,r,opt,y,w);
}
int main(){
// freopen("input.txt","r",stdin);
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=1 ; i<=n ; i++){
int w,v;
cin>>w>>v;
a[w].push_back(v);
}
for(int i=1 ; i<=300 ; i++){
sort(a[i].rbegin(),a[i].rend());
s[i].resize(a[i].size()+1);
for(int j=1 ; j<=a[i].size() ; j++)
{
s[i][j]=s[i][j-1]+a[i][j-1];
}
}
for(int i=1; i <=300 ; i++){
for(int k=0 ; k<i; k++)
f(k,0,m/i+1,0,m/i+1,i);
}
long long ans=0;
for(int i=1 ; i<=m ; i++){
cout<<(ans=max(ans,dp[300][i]))<<" ";
}
return 0;
}
Subset Sum Problem
Subset Sum Problem은 정수 집합에서 합이 $W$가 되는 부분집합을 고를 수 있는지 계산하는 문제입니다. 일반적인 경우 동적계획법으로 $O(NW)$에 해결할 수 있으며 특수한 조건이 붙으면 더 효율적으로 해결할 수 있습니다. 모든 원소가 $D$이하라고 할 때 일반적인 동적계획법으로는 $O(N^2D)$이지만 1999년 발표된 Pisinger의 논문에 의하면 $O(ND)$에 해결할 수 있습니다.
$w_0+w_1+…+w_k < W$가 되도록 하는 최대의 $k$를 생각합시다. 이 때 집합(중복을 허용하는) $\lbrace w_0,w_1,…,w_k \rbrace$의 합이 $\left[W-D,W+D\right]$ 범위 안에 들어가도록 유지시키면서 집합에 원소를 추가하거나 제거하여 답을 얻어낼 수 있습니다. 합이 $W$보다 크다면 수를 제거하고 $W$보다 작다면 수를 추가하면 되기 때문입니다. 이제 집합에 수를 추가하거나 제거하는 것을 $DP$를 이용해 효율적으로 계산할 것 입니다. $DP$를 다음과 같이 정의합시다.
$DP[t][r]=\lambda_0w_0+\lambda_1w_1+…+\lambda_{r-1}w_{r-1}=t$ 이고 $\lambda_i\in\lbrace 0,1\rbrace $일 때 $\lambda_0=\lambda_1=…=\lambda_l=1$ 을 만족하도록 하는 최대 $l$
이러면 $DP[t][r+1]=l,DP[t+w_{r+1}][r+1]=l,dp[t-w_{l’}][r]=l’$ 이라는 transition이 성립합니다. $DP[t][r+1]=DP[t][r]$은 다음 수를 추가하지 않는 것, $DP[t+w_{r+1}][r+1]=DP[t][r]$은 다음 수를 추가하는 것, $dp[t-w_{l’}][r]=l$은 이미 존재하는 수를 제거하는 것입니다. 하지만 단순히 $DP$를 계산하면 $O(N^2D)$ 입니다. 따라서 최적화를 해야합니다. 원소를 추가하는 상태전이는 $O(1)$이니 원소를 제거하는 상태전이만 효율적으로 바꾸어 봅시다. $DP[t][r-1]\leq DP[t][r]$임은 자명합니다. $DP[t][r-1]$에서 $DP[t-w_k][k]$로 transition하는 경우를 생각해봅시다. 이 때 $DP[t][r]$에서는 $DP[t-w_k][k]$로 transition할 필요가 없습니다. 따라서 원소를 제거하는 상태전이는 amortized하게 최적화되어 전체 $O(ND)$가 됩니다.
dp 상태 개수가 $O(ND)$, 상태전이 횟수가 $O(ND)$로 전체 문제를 $O(ND)$에 해결할 수 있습니다. 연습문제로는 NCPC20201E가 있습니다. 실제로 구현할 때에는 토글링을 해야합니다.
제가 구현한 Pisinger Algorithm의 코드로 글을 마무리 하도록 하겠습니다.
int knapsack(vector<int> w, int t){
int D=*max_element(w.begin(),w.end());
int n=w.size();
int l;
int s=0;
for(l=0 ; l<n ; l++){
s+=w[l];
if(s>t)break;
}
if(s>t)s-=w[l];
if(s==t)return t;
for(int i=0 ; i<=2*D ; i++)
dp[1][i]=dp[0][i]=-1;
dp[0][D+s-t]=l;
for(int r=l-1 ; r<n-1 ; r++){
for(int i=0 ; i<=D ; i++){
dp[1][i]=max(dp[1][i],dp[0][i]);
if(i+w[r+1]<=2*D)
dp[1][i+w[r+1]]=max(dp[1][i+w[r+1]],dp[0][i]);
}
for(int i=2*D ; i>=D ; i--)
for(int j=dp[1][i]-1 ; j>=dp[0][i] && j>=0 ; j--)
if(i-w[j]>=0)
dp[1][i-w[j]]=max(j,dp[1][i-w[j]]);
for(int i=0 ; i<=2*D ; i++)
dp[0][i]=dp[1][i];
}
int ans=0;
for(int i=0 ; i<=D ; i++)
if(dp[0][i]>=0)ans=i;
return t+ans-D;
}
참고한 글
https://codeforces.com/blog/entry/98663 https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349?via%3Dihub https://moonrabbit2.tistory.com/3