배낭 문제(knapsack problem)

배낭 문제의 정해가 원래 평범한 배낭과 같다고 생각했는데,

백준 7579 앱을 풀면서

(처음에는 어디선가 본 배열 선언에 대한 제한 때문에 생각해 다른 방법을 찾게 되었다.)

정해를 알게 되어 글을 쓴다.

평범한 배낭 문제로 예를 들어보면,

원래 코드는 다음과 같이 작성했다.

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> bag;
bool avail[100001];
int used[100001][101];
int dp[100001];
int N;
int K;
int wv[2];
int j;

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N >> K;
	avail[0]=true;
	for(int i=0;i<N;i++){
		cin >> wv[0] >> wv[1];
		bag.push_back(make_pair(wv[0], wv[1]));
	}
	for(int i=1;i<=K;i++){
		for(j=0;j<bag.size();j++){
			if(i-bag[j].first>=0 && avail[i-bag[j].first]){
				if(used[i-bag[j].first][j]==0){
					dp[i]=dp[i-bag[j].first]+bag[j].second;
					copy_n(used[i-bag[j].first],101,used[i]);
					used[i][j]++;
					j++;
					avail[i]=true;
					break;
				}
			}
		}
		for(;j<bag.size();j++){
			if(i-bag[j].first>=0 && avail[i-bag[j].first]){
				if(dp[i]<dp[i-bag[j].first]+bag[j].second){
					if(used[i-bag[j].first][j]==0){
						dp[i]=dp[i-bag[j].first]+bag[j].second;
						copy_n(used[i-bag[j].first],101,used[i]);
						used[i][j]++;
						avail[i]=true;
					}
				}
			}
		}
	}
	sort(dp,dp+K+1);
	cout << dp[K];
}

현재 가격 $i$에서 가방 속 모든 물건을 탐색하여 이 가격에서는

어떤 물건이 사용되었는지 확인하는 배열을 사용하는 방식이다.

물건의 중복 체크를 위해 bool 배열을 따로 써야 하는 불편함이 있다.

백준 7579 앱를 보자.

$dp$테이블을 2차원으로 늘려 효율적인 방식으로 처리한다.

$DP(i,j)$는 $i$번째 앱까지 사용했을 때에 비용 $j$로

얻을 수 있는 최대 메모리이다.

비용의 최댓값은 $100(하나당최대앱비용)*100(최대앱개수)$이므로

$DP$배열은 $DP[100][100*100]$으로 선언해주어

$n$개의 앱마다 점화 관계를 사용해 풀어주면 된다.

앱을 $i$번째까지 사용했을때 어떤 비용 $j$에 대하여

$DP(i,j)=max(DP(i-1,j),DP(i-1,j-apps[i]))$으로 나타낸다.

$i$번째 앱을 탐색할 때 $j$를 0부터 10000까지 탐색해주어야 한다.

앱을 모두 사용했을 때 $m$을 넘거나 같게 하는 비용 $j$의 최솟값을

출력해준다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,m;
int dp[100][10001]={0,};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    vector<pair<int, int>> apps(n); //mem cost
    for(int i=0;i<n;i++) cin >> apps[i].first;
    for(int i=0;i<n;i++) cin >> apps[i].second;
    dp[0][apps[0].second]=apps[0].first;
    for(int i=1;i<n;i++){
        for(int j=0;j<10001;j++){
            dp[i][j]=dp[i-1][j];
            if(j-apps[i].second>=0){
                if(dp[i-1][j-apps[i].second]!=0) dp[i][j]=max(dp[i][j],dp[i-1][j-apps[i].second]+apps[i].first);
                else dp[i][j]=max(dp[i][j],apps[i].first);
            }
        }
    }
    for(int i=0;i<10001;i++) if(dp[n-1][i]>=m){cout << i;return 0;}
    return 0;
}