[백준] 23061번 : 백남이의 여행 준비 - C++

문제

https://www.acmicpc.net/problem/23061

23061번: 백남이의 여행 준비

---

코드

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

using namespace std;

pair<int, int> things[101];
int bags[101];
double h[101];
int N, M;
int W = 0;
int V = 0;
int value[101][1000001];

void dp(int bagW)
{
    //memset(value, 0, sizeof(value));
    for(int i = 1 ; i<=N ; i++){
            for(int j = 1 ; j<=bagW ; j++){
                int wi = things[i].first;
                int vi = things[i].second;
      
                if(wi > j)
                    value[i][j] = value[i-1][j];
                  else{
                    value[i][j] = max(value[i-1][j], vi+value[i-1][j-wi]);
                }
                
            }
        }
    //return value[N][bagW];
}

int main()
{
    //cin >> N >> M;
    scanf("%d %d",&N, &M);
    
    for(int i = 1; i<=N;i++)
    {
        scanf("%d %d",&things[i].first, &things[i].second);
        //cin>>things[i].first >> things[i].second;
    }
    int max= 0;
    for(int i = 1; i<=M; i++)
    {
        cin >> bags[i];
        if(bags[i]>max) max = bags[i];
    }
    dp(max);
    max = 1;
    for(int i = 1; i<=M; i++)
    {
        h[i] = (double)value[N][bags[i]]/ (double)bags[i];
        if(h[i]>h[max]) max = i;
    }
    cout<<max;
}

 

Knapsack Problem 알고리즘을 사용하여 해결하였다.

다이나믹 프로그래밍을 사용하여 이차원 테이블을 순회한다.

Knapsack Problem의 테이블은 코드에서 value로 선언해주었다.

 

처음에는 가방 크기별로 value테이블을 새로 만들어야 한다고 생각해서 시간초과가 떴다!!!

하지만 그럴 필요 없이, 입력받은 가방의 크기 중에서 가장 큰 것을 기준으로 테이블을 만들면

인덱스를 통해 접근하여 효율성을 구해주면 된다.