algospot PACKING

문제 링크입니다:

최근 풀었던 문제들처럼 동적계획법을 활용하여 문제를 풀면 됩니다. 또한 backtracking(역추적)을 통해 선택한 물건들을 유추할 수 있습니다.

/*

여행을 갈 때 캐리어 하나만 가지고 가려고 한다.

가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를

조사해 캐리어의 용량 w이하로 절박도를 최대화할 수 있는 물거들의 목록을

계산하는 프로그램을 작성하시오

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <cstring> //memset

using namespace std;

 

int total, capacity; //총 아이템 양과 가방 용량

int volume[100], need[100]; //물건의 부피와 절박도

int cache[1001][100];

string name[100];

 

//캐리어에 남은 용량이 capacity일 때 item 이후의 물건들을

//담아 얻을 수 있는 최대 절박도의 합을 반환

int pack(int capacity, int item)

{

        //기저 사례:더 담을 물건이 없을 때

        if (item == total)

               return 0;

        int &result = cache[capacity][item];

        if (result != -1)

               return result;

        //이 물건을 담지 않을 경우

        result = pack(capacity, item + 1);

        //이 물건을 담을 경우

        if (capacity >= volume[item])

               result = max(result, pack(capacity - volume[item], item + 1) + need[item]);

        return result;

}

 

//여행 짐싸기 문제의 답 역추적하는 재귀 호출 알고리즘

void reconstruct(int capacity, int item, vector<string> &picked)

{

        //기저 사례:모든 물건 고려

        if (item == total)

               return;

        if (pack(capacity, item) == pack(capacity, item + 1)) //item을 선택하지 않아도 최대 절박도 동일(즉, item 선택 안해도 된다)

               reconstruct(capacity, item + 1, picked);

        else

        {

               picked.push_back(name[item]); //item 선택

               reconstruct(capacity - volume[item], item + 1, picked);

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               vector<string> picked;

               cin >> total >> capacity;

               if (total < 1 || total>100 || capacity < 1 || capacity>1000)

                       exit(-1);

               for (int j = 0; j < total; j++)

               {

                       cin >> name[j] >> volume[j] >> need[j];

                       if (name[j].empty() || name[j].size() > 21 || volume[j] < 1 || volume[j]>1000 || need[j] < 1 || need[j]>1000)

                              exit(-1);

               }

               memset(cache, -1, sizeof(cache));

               reconstruct(capacity, 0, picked);

               cout << pack(capacity, 0) << " " << picked.size() << endl;

               for (int j = 0; j < picked.size(); j++)

                       cout << picked[j] << endl;

               //cout<<endl; 보기 좋게하려고 개행을 했는데 이렇게 하면 오답 처리됩니다

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략