평범한 배낭

Description

이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

Input

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.

Output

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

Example

입력 예제
4 7
6 13
4 8
3 6
5 12
출력
14

Code_1 Recursion

def knapSack(W, wt, val, n):

    # BaseCase 
    if n == 0 or W == 0:
        return 0

    # If weight of the nth item is more than Knapsack of capacity W, then this item cannot be included in the optimal solution
    if (wt[n-1] > W):
        return knapSack(W, wt, val, n-1)

    # return the maximum of two cases:
    # case 1 : nth item included
    # case 2 : not included
    else:
        return max(
            val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
            knapSack(W, wt, val, n-1)
        )

Code_2 DP

def knapsack_dp(W, wt, val, n):
    dp = []
    for i in range(n+1):
        row_list = []
        for j in range(W+1):
            row_list.append(0)
        dp.append(row_list)
    # dp[i][j] : 배낭의 용량이 j 일 때, i번 물건까지 담을 수 있는 경우의 최대 케이스
    for i in range(1, n+1):
        for j in range(1, W+1):
            if wt[i-1] > j: # 물건 i 의 무게가 배낭의 용량 j를 초과
                dp[i][j] = dp[i-1][j]
            else : # 물건 i의 무게를 배낭에 담을지 담지 말지 비교
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1])

    return dp[n][W]

Thoughts

본 문제는 배낭문제(Knapsack Problem)으로 알고리즘을 수업시간에 공부할 때 한 번쯤은 공부하게 되는 내용이고 DP를 한 번 정리할 겸 풀어보았다.
이 문제는 다양한 방법으로 풀 수 있는데 나는 두 가지 방법을 사용해 보았고, 백준 채점에서는 recursion을 사용했더니 TLE가 나왔다.

먼저 재귀로 푼 방법은,
물건을 하나씩 따져봐서 n번째 물건을 생각했을때, 두가지의 경우가 있음을 우리는 알 수 있다.
첫 번째 경우 : n번째 물건을 포함시킨다.
두 번째 경우 : n번째 물건을 포함시키지 않는다.
아주 간단한데, 결국 n번째를 포함시킨 결과와 n번 째를 포함시키지 않은 결과의 크기를 비교하는 것이다.
Knapsack함수에 배낭에 남은 용량(넣을 수 있는 양) W와 물건의 무게 리스트:wt, 물건의 가치 리스트:val, 몇 번째 물건인지를 나타넬 인덱스 n을 파라미터로 사용한다. 차근 인덱스를 줄여가다가 0번째 즉 모든 물건을 다 따졌거나 더이상 배낭에 담을 공간이 없는 경우 W=0일 때 return하는 베이스 케이스를 지정하는 recursion함수를 사용하면 답을 쉽게 구할 수 있다.
가장 직관적으로 생각하기 쉬운 방법인거 같다.

다음은 동적계획법(Dynamic Programming)으로 푼 방법이다.
Knapsack 문제는 처음 DP를 배웠을 때, 공부를 했었기 때문에 다시 풀 때도 가뿐할 것 같았지만 다시 봐도 쉽게 머리에 떠오르지 않았다.

DP에 대해서 잠시 정리를 하면, 분할 정복 알고리즘과 비슷한 접근방식으로 문제를 푸는 알고리즘(?)을 가리키는데, 쉽게 생각하면 문제를 부분 구조화시켜가며 푸는 일종의 방법을 말한다. 따라서 계속해서 부분적으로 subproblems를 만들어 가도록 어떻게 설계할 것인가가 가장 어렵고 핵심이다.
대신 그냥 분할 정복과의 차이점은 DP는 계속해서 세분화 시킨 subproblems를 해결하기 쉬운 순간까지 분할 시켜 문제를 해결한 다음 그 계산 결과들을 이용해서 효율성을 올리는 것이다. 무슨 말이냐 하면, 일종의 테이블과 같은 저장 공간을 따로 두어서 세분화된 문제의 답을 메모이제이션(기억해두기?)을 이용해서 똑같은 계산을 반복하지 않도록 한다는 의미이다.

이게 말로는 그렇게 이해할 수 있다해도 항상 문제를 풀 때는 그래서 어떻게 식을 세울지가 제일 어렵다.

위의 Knapsack문제에서는 subproblem으로 설계하는 법이 또 의외로 간단하다.

임의의 i번 째 물건을 생각하자, 이 때의 무게를 wi라 할 때 wi가 배낭에 들어갈 수 있는 용량을 초과하는지 초과하지 않는지 두가지 경우를 생각할 수 있다. 만약 그 무게가 배낭에 들어갈 수 있는 용량을 초과한다면 i번째 물건은 담을 수 없을것이고, i번째 물건을 담을 수 있다면, 담는게 좋을지 담지 않는게 좋을지 따져보면 된다.

그래서 2차원 수열을 하나 만든다.
dp[i][j] 는 배낭의 남은 용량이 j일 때, i번째 물건까지 있을 때 구할 수 있는 최대 가치이다.
그냥 이런식으로 구해야할 답인 W의 용량을 가진 가방에 N개의 물건이 있을 때 담을 수 있는 최대가치를 세분화 시킨 것 뿐이다.
따라서 주어진 물건의 수 N만큼의 세로와 주어진 용량 W만큼의 가로 길이를 가지고 저장 테이블을 만드는 것이다.
이렇게 만들어 놓은 테이블에서 주어진 물건의 수가 1번 까지이고, 이때 가방의 남은용량이 1인 가장 작은 subproblem부터 시작한다.
따라서 주어진 물건의 갯수가 1번일 때, 첫번 째 row의 테이블이 만들어지고, 2번일 때 두번 째 row, 3번일 때 세번째 row,... 마지막 N번일때 마지막 테이블 row가 완성될 것이고 우리의 초기의 관심사인 N개의 물건으로 W의 용량을 가졌을 때 최대 가치는 테이블의 가장 우측 아래의 값인 dp[N][W]가 될 것이다.