배낭문제 정리

배낭문제는 쪼갤 수 있는 배낭문제와 쪼갤 수 없는 배낭문제가 있다.

쪼갤 수 있는 배낭문제는 무게가 넘치면 쪼개서 넣기 때문에 공간이 부족해서 못 넣는 경우가 없기 때문에,
가치가 큰 값을 먼저 고려하는 탐욕 알고리즘을 적용이 가능하다.

하지만

쪼갤 수 없는 배낭문제의 경우 가치가 가장 크거나, 작은 물건을 넣더라도 공간의 문제로 최적의 답을 얻지 못하는 경우가 있다.

그렇기에 모든 경우의 수를 찾아야 하는데,

#include <iostream>
#include <algorithm>

using namespace std;

// 물품의 수는 100개 이하
int weight[100];
int value[100];
int testcase, totalweight;

//완전탐색
int BF(int now_element, int now_weight) {

    // 원소를 모두 봤다면 종료(종료조건)
	if (now_element == testcase) return 0;
    
    int n1 = 0;
    // 추가해도 최대 무게를 안넘기는 경우
    if (now_weight + weight[now_element] <= totalweight) {
    // 추가하고 다음 원소에서 다시 검색
        n1 = value[now_element] + BF(now_element + 1, now_weight + weight[now_element]); 
    }
    // 아니라면 추가하지 않고 다음 원소 검색
    int n2 = BF(now_element + 1, now_weight); 
    return max(n1, n2);
}
int main() {
    cin >> testcase >> totalweight;
    
    // 물품 무게, 가치 저장
    for (int i = 0; i < testcase; i++) {
        cin >> weight[i] >> value[i];
    }
    
    cout << BF(0, 0);
    
    return 0;
    
}

이렇게 재귀나 이중for문을 사용할 경우 모든 경우의 수를 찾기 때문에 이미 찾은 경우와 같은 연산을 해야할 때가 있는데, DP는 이미 찾은 경우를 따로 저장해두어 완전탐색의 연산량을 줄여주는 역할을 한다.

#include <iostream>
#include <algorithm>

using namespace std;

// 물품의 수는 100개 이하
int weight[100];
int value[100];
int testcase, totalweight;

int dp[101][100001];
//완전탐색
int BF(int now_element, int now_weight) {

	if (dp[now_element][now_weight] > 0) return dp[now_element][now_weight];
    // 원소를 모두 봤다면 종료(종료조건)
	if (now_element == testcase) return 0;
    
    int n1 = 0;
    // 추가해도 최대 무게를 안넘기는 경우
    if (now_weight + weight[now_element] <= totalweight) {
    // 추가하고 다음 원소에서 다시 검색
        n1 = value[now_element] + BF(now_element + 1, now_weight + weight[now_element]); 
    }
    // 아니라면 추가하지 않고 다음 원소 검색
    int n2 = BF(now_element + 1, now_weight); 
    return dp[now_element][now_weight] = max(n1, n2);
}
int main() {
    cin >> testcase >> totalweight;
    
    // 물품 무게, 가치 저장
    for (int i = 0; i < testcase; i++) {
        cin >> weight[i] >> value[i];
    }
    
    cout << BF(0, 0);
    
    return 0;
    
}