최적화 문제의 결과 출력 - 배낭 문제(Knapsack Problem)

링크: https://www.algospot.com/judge/problem/read/PACKING

algospot.com :: PACKING

---

 최적화 문제에서 경로의 가짓수를 센다거나, 최대값을 구하는 일은 쉽습니다. 그러나 실제 경로를 출력해야한다면 어떨까요? 완전탐색 알고리즘에 동적계획법을 적용할 때 단지 캐시만 추가하여 전체 흐름에는 크게 변화가 없었던 것처럼, 결과를 출력할 때도 코드를 크게 바꾸지 않습니다. 단지 캐싱 과정에서 저장의 용이성을 위해 어느정도 포기했던 정보를 다시 재구축하는 코드만 있으면 됩니다.

 위의 유명한 배낭 문제는 동적계획법을 이용한 최적화로 풀 수 있습니다.

<Python3 소스 코드>

import sys
rl = lambda: sys.stdin.readline()


def pack(capacity, idx=0):
	# 기저 사례
    if idx >= len(items):
        return 0
    # 메모이제이션
    if cache[capacity][idx] != -1:
        return cache[capacity][idx]
    # 부분 문제 풀이
    MAX = pack(capacity, idx + 1)
    weight, req = items[idx][1], items[idx][2]
    if items[idx][1] <= capacity:
        MAX = max(MAX, pack(capacity - weight, idx + 1) + req)
    cache[capacity][idx] = MAX
    return cache[capacity][idx]
            
def reconstruct(capacity, idx, ret=None):
    if idx == len(items): return ret
    # 빈 리스트를 디폴트 인자값으로 주면 안됩니다.
    # 함수는 호출 시점에 평가되기 때문에 모든 함수가 리스트의 주소를 공유합니다.
    if ret is None:
        ret = []
    if pack(capacity, idx) == pack(capacity, idx + 1):
        ret = reconstruct(capacity, idx + 1, ret)
    else:
        ret.append(items[idx][0])
        ret = reconstruct(capacity - items[idx][1], idx + 1, ret)
    return ret
            
    
for _ in range(int(rl())):
    N, W = list(map(int, rl().split()))
    items = []
    for _ in range(N):
        name, weight, req = rl().split()
        items.append((name, int(weight), int(req)))
    cache = [[-1 for _ in range(100)] for _ in range(1000)]
    
    MAX = -1
    for i in range(len(items)):
        MAX = max(MAX, pack(W, i))
    picked = reconstruct(W, 0)
    N = len(picked)
    
    print(MAX, N)
    for i in range(N):
        print(picked[i])

위의 pack(capacity, idx) 함수가 부분 문제를 풀이하는 반면, reconstruct(capacity, idx, ret) 함수는 부분문제 풀이 결과를 비교하여 정보를 재건축합니다. 만약 reconstruct(capacity, 0, ret)이 reconstruct(capacity, 1, ret)과 같으면 0번째 아이템은 있으나 마나 하다는 의미이므로 건너뛰어도 되겠지요. 미리 캐싱을 해놓았기 때문에 재호출 시에는 O(1)으로 연산할 수 있습니다. 

 이런 식으로 동적계획법으로 작성한 알고리즘에서 실제 경로를 출력하는 것은 생각보다 간단합니다. 별도의 배열 혹은 캐싱한 정보를 이용하여 각 상황에 선택했던 최적의 선택을 다시 따라갈 수만 있으면 됩니다.

 

<C++ 소스코드>

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

int cache[1001][101] = { -1 };

int pack(const int capacity, const int idx, 
	const vector<int>& weight, const vector<int>& req)
{
	if (idx == weight.size()) return 0;
	int& ret = cache[capacity][idx];
	if (ret != -1) return ret;

	int MAX = pack(capacity, idx + 1, weight, req);
	if (weight[idx] <= capacity) 
		MAX = max<int>(MAX, pack(capacity - weight[idx], idx + 1, weight, req) + req[idx]);
	ret = MAX;
	return ret;
}

vector<string> reconstruct(const int capacity, const int idx, vector<string>& picked,  
	const vector<string>& name, const vector<int>& weight, const vector<int>& req)
{
	if (idx == name.size()) return picked;
	if (pack(capacity, idx, weight, req) == pack(capacity, idx + 1, weight, req))
		picked = reconstruct(capacity, idx + 1, picked, name, weight, req);
	else
	{
		picked.push_back(name[idx]);
		picked = reconstruct(capacity - weight[idx], idx + 1, picked, name, weight, req);
	}
	return picked;
}

int main(void)
{
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++)
	{
		int N, W;
		vector<string> name;
		vector<string> picked;
		vector<int> weight, req;
		for (int i = 0; i < 1001; i++)
			fill_n(cache[i], 101, -1);
		scanf("%d%d", &N, &W);
		for (int i = 0; i < N; i++)
		{
			char n[101];
			int w, r;
			scanf("%s%d%d", n, &w, &r);
			name.push_back(n); weight.push_back(w); req.push_back(r);
		}
		int max_req = -1;
		for (int idx = 0; idx < weight.size(); idx++)
			max_req = max<int>(max_req, pack(W, idx, weight, req));
		picked = reconstruct(W, 0, picked, name, weight, req);
		printf("%d %d\n", max_req, picked.size());
		for (string name : picked)
			cout << name << "\n";
	}
}