알고리즘[C++] 0-1 knapsack problem with Backtracking(백트래킹)

문제

교재와 강의자료를 참고하여 0-1 배낭 문제를 해결하는 Algorithm 5.7을 완성하시오.

단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오.
또한, 알고리즘의 출력은 알고리즘의 실행 단계별로
상태 공간 트리의 각 노드에서의 상태를 출력해야 함에 주의하시오.

입력

첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다.
두 번째 줄에 n개의 아이템 무게 w [i]가 주어진다.
세 번째 줄에 n개의 아이템 이익 p [i]가 주어진다.

출력

첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오.
노드 상태는 다음과 같은 순서로 출력한다.
i weight profit bound maxprofit
상태를 출력하는 순서는 Algorithm 5.7의 노드 실행 순서이다. (즉, DFS with Pruning의 노드 순회 순서임)
노드의 상태 출력이 끝나는 다음 줄에 최대이익을 출력한다.
이후로 배낭에 담은 아이템을 한 줄에 하나씩 무게와 이익 순서로 출력한다.
아이템을 출력하는 순서는 처음에 단위무게당 이익으로 정렬한 순서대로 출력함에 주의할 것.

 

문제 해석

1. 백트래킹 기법을 활용한 0-1 knapsack problem
2. 모든 문제에서 그랬듯 단위 무게당 이득을 내림차순으로 정렬함.
3. 모든 노드를 방문하는 DFS방식을 사용함.
4. 효율성을 위해서 weight(현재 담긴 보석들의 무게)와 W(가방의 용량)을 비교해서 적절한 노드를 탐색함.
   1. 내가 현재 담은 무게와 다음번에 담을 보석의 무게가 W보다 작아야 함.
5.  Bound와 Maxprofit을 설정해서 탐색함.
   1. Bound는 기대되는 이익의 상한선.
      1. Bound가 Maxprofit보다 작다면 그 노드들의 뿌리와 노드는 탐색할 필요가 없다.
   2. Maxprofit은 내가 방문한 노드들 중에서 가장 큰 profit.
      1. 만약 내가 탐색하려는 노드의 profit이 Maxprofit보다 작으면 탐색할 필요가 없다. 
   3. Bound가 Maxprofit보다 커야 함.
      1. 만약 Bound가 Maxprofit보다 작거나 같다면 더이상 탐색할 필요가 없다.
6. 담았을 때와 안 담았을 때를 구별해줌.

구현

1. Weight와 Profit을  profit [i]/weight [i]가 큰 순서대로 정렬함.
2. 가지치기 조건
   1. Weight가 W보다 클 때. Weight는 내가 담은 보석들의 무게 합
   2. Bound가 maxprofit보다 작을 때

코드

/*
1.백트래킹을 활용한 배낭문제
2.모든 문제에서 그랫듯 단위무게당 이득을 내림차순으로 정렬함..
3. 모든 노드를 방문하는 DFS방식으로 문제를 풀이할예정
4. weight(현재 담은 무게)와 W(가방의 용량)을 비교하면서 가지치기
5. Bound와 Maxprofit을 설정해서 Bound(기대되는 이득?)이 Maxprofit보다 작으면 굳이 탐색할 필요가 없음. 가지치기
6. 시간복잡도는 세타(2^n)
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, W, maxprofit, total, bound;
vector<int> weight;
vector<int> profit;
vector<int> include(10000);
vector<int> best(10000);
bool promising(int i, int Profit, int Weight, int &bound);
void knapsack_4(int i, int Profit, int Weight);
int main()
{
    cin >> n >> W;
    weight.resize(n + 1);
    profit.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> profit[i];
    }
    for (int i = 1; i <= n; i++) //단위무게가 무거운 순으로 정렬함.
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (profit[i] / weight[i] < profit[j] / weight[j])
            {
                swap(profit[i], profit[j]);
                swap(weight[i], weight[j]);
            }
        }
    }
    knapsack_4(0, 0, 0);
    cout << maxprofit << endl;
    int cnt = 0, temp = 0;
    for (int i = 1; i <= n; i++)
    {
        if (best[i] == 1) // best가 1인경우가 넣었다는 뜻임.
        {
            cnt++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (best[i] == 1)
        {
            temp++;
            if (temp != cnt)
                cout << weight[i] << " " << profit[i] << endl;
            else
                cout << weight[i] << " " << profit[i];
        }
    }
    // while (getchar() != '\n');
}
void knapsack_4(int i, int Profit, int Weight)
// root 방문하고 profit이랑 weight 박고 bound설정해줘야함. bound는 내가 담을수 있는 최대한의 가치
{
    if (Weight <= W && Profit > maxprofit)
    {
        maxprofit = Profit;
        copy(include.begin(), include.end(), best.begin()); //best에 경로저장. 1이면 담고 0이면 안담은것.
    }
    if (promising(i, Profit, Weight, bound))
    {
        include[i + 1] = true;                                             //넣을 경우 트루
        knapsack_4(i + 1, Profit + profit[i + 1], Weight + weight[i + 1]); //담는경우
        // include = 0,1,0,1 가 최대값이다.
        include[i + 1] = false;            //넣지않을때
        knapsack_4(i + 1, Profit, Weight); //안담앗을때는
    }
}
bool promising(int i, int Profit, int Weight, int &bound) // Profit은 내가 지금 담은 가치 Weight는 내가 담은 용량
{
    if (Weight > W) //내가 담은 무게가 가방용량보다 무겁다면 ? 다시 되돌아가야함.
    {
        cout << i << " " << Weight << " " << Profit << " " << bound << " " << maxprofit;
        cout << endl;
        return false;
    }
    else //만약 담을 수있다면?
    {
        //무게가 초과안할때까지 bound에 넣어줌.
        //현재담을 무게를 제외하고 bound에 넣고 넣은 뒤에 넣어줌.

        int k = i + 1; //현재의 가방을 제외하고 뒤부터 넣어준다는 뜻임.
        bound = Profit;
        total = Weight;
        while (k <= n && total + weight[k] <= W) // total+ 다음 담을 용량이 W보다 작아야함. 그게 크다면 따로 조건을 걸어서 남는 무게만큼 bound에 넣어주면됨.
        {
            total += weight[k];
            bound += profit[k];
            k++;
        }
        if (k <= n) //가방을 끝까지 돌지 못햇는데 만약 무거워서 while을 나갔다면 bound는 쪼개서 넣어줌.
        {
            bound += (W - total) * (profit[k] / weight[k]);
        }
        cout << i << " " << Weight << " " << Profit << " " << bound << " " << maxprofit;
        cout << endl;
        if (bound > maxprofit) // bound값은 무조건 maxprofit보다 커야 탐색을 함/
            return true;
        else              //작으면 탐색할 이유가 없음.
            return false; // bound가 maxprofit보다 클때 promising 가능.
    }
}

 

느낀 점 : 배낭 문제를 푸는 난이도는 Greedy << Backtracking << DP인 것 같다.

DP가 좀 취약한 듯..ㅠ