C++/ Knapsack 알고리즘

 

냅색 알고리즘이란?

 조합 최적화의 유명한 문제이다.

간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

한정 조건을 가지고, 다수의 조합이 가능할 때 모든 조합을 고려해서 최적의 해를 구하는 문제의 해결법.

 

냅색 문제를 풀 때는 Top-down 방식과 Bottom-up 방식 적용이 가능하다.

Top-down 방식에서는 DFS를 이용하는 것이 일반적이며 메모이제이션을 추가하는 것이 효율성을 증대시킨다. 

 

<최단 경로 문제>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
//top-down
int arr[21][21], dy[21][21];

int dfs(int x, int y){
    if(dy[x][y]>0) return dy[x][y];
    if(x==0 && y==0) return arr[0][0];
    else{
        if(y==0) return dy[x][y] = dfs(x-1,y)+arr[x][y];
        else if(x==0) return dy[x][y] = dfs(x,y-1)+arr[x][y];
        else return dy[x][y] = min(dfs(x-1,y),dfs(x,y-1)) + arr[x][y];
    }
}
int main(){
    int n, cnt =0;
    cin>>n;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
    }

    cout<<dfs(n-1,n-1);
    return 0;
}

 

Bottom-up 방식에서는 Loop를 돌려서 다이나믹 프로그래밍으로 푸는 것이 일반적이다.

대표적으로 동전 문제와 최대 점수 구하기 문제가 있다.

 

www.acmicpc.net/problem/2294

2294번: 동전 2

 

동전을 최소 개수로 사용하면서 목표 값을 맞춰야 하는 문제이다

일차원 배열 하나만 가지고 풀 수 있는 문제이며, 메모이제이션으로 계속 최솟값을 갱신해 주기만 하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
//coin algorithm , knapsack
using namespace std;

int main(){
    int n, m;
    cin>>n;
    vector<int> coin(n);
    cin>>m;
    for(int i=0;i<n;i++){
        cin>>coin[i];
    }
    vector<int> dy(m+1,1000);
    dy[0]=0;

    for(int i=0;i<n;i++){
        for(int j=coin[i];j<=m;j++){
            dy[j] = min(dy[j],dy[j-coin[i]]+1);
        }
    }
    cout<<dy[m];
    
    return 0;
}

 

dy[j] = min(dy[j], dy[j-coin[i]]+1

 

코드에서 이 부분만 이해가 간다면 비슷한 문제는 쉽게 해결할 수 있을 것이다.

 

 

문제2 : n개의 문제가 주어졌을 때, 제한시간 m 안에 풀어서 나올 수 있는 점수의 최댓값을 구하라.

(출처 인프런)

- n개의 문제는 각기 풀 때 걸리는 시간 pt와 풀어서 얻을 수 있는 점수 ps가 주어진다.

- 한 문제는 한 번 밖에 풀지 못한다

 

이 조건으로 문제를 풀었을 때, 앞에서부터 문제를 풀게 되면 점수가 계속 중복 갱신되는 문제가 발생한다.

따라서 목표 시간인 m 에서부터 문제를 풀어서 다이나믹 테이블을 완성하면 문제가 해결된다.

 

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

int main(){
    int n, m, ps, pt;
    cin>>n>>m;
    vector<int> dy(m+1);

    for(int i=0;i<n;i++){
        cin>>ps>>pt;
        for(int j=m;j>=pt;j--){
            dy[j-pt] = max(dy[j],ps+dy[j-pt]);
        }
    }
    cout<<dy[m];
    return 0;
}