[boj : 12865]평범한 배낭

[문제] : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

[분류] : 다이나믹 프로그래밍(DP)

 

[구현 방법] :

유명하고(well known) dp문제를 두고 보면 빠지지 않고 나오는 문제 입니다.

흔히 "냅섹(knapsack)"문제라고 불립니다.

물건 하나씩 더해가면서 현재 가방의 무게가 w 일때 최대로 담을 수 있는 가치 p 를 계산해 주면 됩니다.

vector를 이용해서 풀어서 인덱스 값만 주의해서 코드를 짜주시면 큰 무리 없이 짤 수 있을 것 입니다.

좀 더 자세한 설명을 원하시는 분은 링크를 첨부하겠습니다.(도움이 많이 되었던 글입니다)

https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

[DP] 0/1 Knapsack(배낭) 문제

 

[소스] : 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int ans[100][100001];
 
int main()
{
    int n, m, a, b;
    vector<pair<int, int>> weigth_profit;
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)    {
        cin >> a >> b;
        weigth_profit.push_back({ a,b });
    }
 
    for (int i = 0; i < n; i++)    {
        for (int j = 0; j <= m; j++){
            if (i == 0)
            {
                if (weigth_profit[i].first <= j)
                    ans[i][j] = weigth_profit[i].second;
                continue;
            }
            //넣으려는 물건의 무게가 가방의 무게보다 작거나 같아야 된다.
            if (weigth_profit[i].first <= j)
                ans[i][j] = max(ans[i - 1][j], weigth_profit[i].second + ans[i - 1][j - weigth_profit[i].first]);
            else
                ans[i][j] = ans[i - 1][j];
        }
    }
    cout << ans[n - 1][m];
    return 0;
}

 

※별개로 꼭 다루고 싶은 부분이 있습니다.

배낭 문제는 DP말고도 브루트 포스(Brute force)로도 정답을 도출을 할 수 는 있습니다.

그러나 지수승의 시간복잡도로 인해 제한된 시간에서는 해결을 하지 못하죠.(이 문제는 브루트포스로 풀려고 하면 시간초과가 발생합니다.)

 

[소스] : 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int n, k;
int ans,cnt,weight,visit[100];
vector<pair<int, int>> v;
 
void DFS(int x);
 
int main()
{    
    cin >> n >> k;
    for(int i=0;i<n;i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({ a,b });
    }
    DFS(0);
    cout << ans;
    return 0;
}
void DFS(int x)
{
    for (int i = x; i < n; i++)
    {
        if (!visit[i] && weight + v[i].first <= k)
        {
            visit[i] = true;
            weight += v[i].first;
            cnt += v[i].second;
            DFS(i);
            visit[i] = false;
            weight -= v[i].first;
            cnt -= v[i].second;            
        }
    }
    ans = max(ans, cnt);
}

브루트 포스로 짠 소스입니다.

이렇게 구현을 하게 되면 DFS함수는 중복 호출이 되는 부분이 발생하게 되죠.

따라서 배낭문제의 브루트포스 시간복잡도는

n개 중 0개선택+n개 중 1개선택+...+n개 중 n개 선택

->nC0+nC1+nC2+....+nCn=2^n

즉,O(2^2) 이 됩니다.

 

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다