[백준]평범한 배낭 여러 알고리즘으로 풀기

0-1 KnapSack Problem

배낭 문제는 가중치를 자를 수 있는 문제인 Fractional KnapSack Problem와 없는 문제로 나뉜다.
이번 글에서는 보석(가중치)를 자를 수 없는 문제만 다룬다.
Fractional일 경우 그리디로 풀 수 있지만 0-1에서는 불가하고 아래 알고리즘으로 풀 수 있다.
1. 부루트포스
2. Dynamic Programming
3. Back Tracking
4. Branch N Bound

DP

#include <iostream>
#include <vector>
using namespace std;

struct Tool {
    int weight;
    int value;
    void initTool(int w, int v) {
		weight = w;
		value = v;
	}
};
vector <Tool> tools;
int knapsackDP(vector<Tool>& tools, int capacity) {
    int n = tools.size();
    //dp[i][w]는 i번째 항목까지 고려한 배낭의 용량이 w일 때 얻을 수 있는 최대 가치
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (tools[i - 1].weight <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - tools[i - 1].weight] + tools[i - 1].value);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

int main() {
    int n,k;
    cin >> n >> k;
	tools.resize(n+1);
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		Tool t;
		t.initTool(w, v);
		tools[i] = t;
	}
    cout <<knapsackDP(tools, k);
    return 0;
}

BackTracking

백트래킹만해서 풀면 시간복잡도가 최악 2^n 이므로 n이 커질수록 효율적이지 않다. 실제로 백준 문제에서 시간 초과가 떠서 시간복잡도를 줄이기 위해 메모제이션을 사용하여 해결하였다.

#include<iostream>
#include<vector>
# include<algorithm>
using namespace std;
int n, k;

struct Tool {
	int weight;
	int value;
	int profit;
	void initTool(int w, int v) {
		weight = w;
		value = v;
		profit= v / w;
	}
};
vector <Tool> tools;
int maxValue = 0;
//memo[Index][Weight]는Index 번째 항목까지 고려하고 현재 무게가 cWeight일 때 얻을 수 있는 최대 가치
vector<vector<int>> memo;

int knapsackBacktrack(vector <Tool> items, int n, int capacity, int currentIndex, int currentWeight) {
	if (currentIndex >= n || currentWeight > capacity) {
		return 0;
	}

	if (memo[currentIndex][currentWeight] != -1) {
		return memo[currentIndex][currentWeight];
	}

	int value1 = 0;
	if (currentWeight + items[currentIndex].weight <= capacity) {
		value1 = items[currentIndex].value + knapsackBacktrack(items, n, capacity,
			currentIndex + 1,
			currentWeight + items[currentIndex].weight);
	}

	int value2 = knapsackBacktrack(items, n, capacity, currentIndex + 1, currentWeight);

	memo[currentIndex][currentWeight] = max(value1, value2);
	return memo[currentIndex][currentWeight];
}
int main() {
	cin >> n >> k;
	tools.resize(n+1);
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		Tool t;
		t.initTool(w, v);
		tools[i] = t;
	}
	memo.assign(n, vector<int>(k+ 1, -1));
	
	cout << knapsackBacktrack(tools, n, k, 0,0);
	return 0;
}

Branch and Bound

분기한정 알고리즘은 어떤 마디에서 확장 여부를 결정할 때
지금까지 구한 답 중에서 가장 좋은 값보다 한계값이 더 좋은 지 검사한다.
BFS 이용-> 더 많은 경우 탐색. 비효율
코드는 이후 첨부 예정

참고링크