bookthief질문 드립니다.

  • swg0110
    swg0110

    안녕하세요 bookthief를 푸는데 i번째부터 n번 째까지 v라는 부피를 가지고 만들수 있는 최대 value를 _arrMaxVal[i][v]에 저장하는 식으로 해서, dynamic programming으로 구현했는데요.

    또 i번째 부터 n번째 것으로 만들수 있는 최대부피랑 최소부피를 각각 저장해서, _arrMaxVal[i][vol]를 구할때 vol이 i부터 n번째 책으로 만들수 있는 최대 부피보다 크거나, 최소부피보다 작으면 탐색을 하지 않는 것으로 했고요. 같을때도 더 이상 탐색하지 않고, 미리 계산해 해놓은 그 때의 value를 리턴하는 방식으로 구현을 했는데요. 시간초과가 발생합니다ㅠㅠ 더 탐색을 줄일방법이 생각나지 않는데 알려주시면 정말 감사하겠습니다.ㅠㅠ 감사합니다

    //
//  main.cpp
//  bookthief
//
//  Created by wongeun on 2015. 10. 30..
//  Copyright © 2015년 wongeun. All rights reserved.
//

#include <iostream>
#include <string.h>

#define MIN     0
#define MAX     1

using namespace std;

int _bookCount;
int _volume;

int* _arrVolume;
int* _arrValue;
int* _arrCount;

int** _arrRemVol;
int** _arrRemVal;

int** _arrMaxVal;

int calcMaxValueSum(int bookIdx, int remainVol);

int main(int argc, const char * argv[]) {
    int caseCount = 0;
    int caseIdx = 0;

    cin >> caseCount;

    while (caseIdx < caseCount) {
        cin >> _bookCount >> _volume;

        _arrVolume = new int[_bookCount];
        _arrValue = new int[_bookCount];
        _arrCount = new int[_bookCount];

        for (int i = 0; i < _bookCount; i++) {
            cin >> _arrVolume[i] >> _arrValue[i] >> _arrCount[i];
        }

        _arrRemVol = new int*[2];
        _arrRemVal = new int*[2];

        _arrRemVol[MIN] = new int[_bookCount];
        _arrRemVol[MAX] = new int[_bookCount];
        _arrRemVal[MIN] = new int[_bookCount];
        _arrRemVal[MAX] = new int[_bookCount];

        _arrRemVol[MIN][_bookCount - 1] = _arrVolume[_bookCount - 1];
        _arrRemVol[MAX][_bookCount - 1] = _arrVolume[_bookCount - 1] * _arrCount[_bookCount - 1];
        _arrRemVal[MIN][_bookCount - 1] = _arrValue[_bookCount - 1];
        _arrRemVal[MAX][_bookCount - 1] = _arrValue[_bookCount - 1] * _arrCount[_bookCount - 1];

        for (int i = _bookCount - 2; i >= 0; i--) {
            if (_arrVolume[i] < _arrRemVol[MIN][i + 1]) {
                _arrRemVol[MIN][i] = _arrVolume[i];
                _arrRemVal[MIN][i] = _arrValue[i];
            }
            else {
                _arrRemVol[MIN][i] = _arrRemVol[MIN][i + 1];
                _arrRemVal[MIN][i] = _arrRemVal[MIN][i + 1];
            }

            _arrRemVol[MAX][i] = _arrRemVol[MAX][i + 1] + _arrVolume[i] * _arrCount[i];
            _arrRemVal[MAX][i] = _arrRemVal[MAX][i + 1] + _arrValue[i] * _arrCount[i];
        }

        _arrMaxVal = new int*[_bookCount];

        for (int i = 0; i < _bookCount; i++) {
            _arrMaxVal[i] = new int[_volume + 1];

            memset(_arrMaxVal[i], 0, (_volume + 1) * sizeof(int));
        }

        int maxValSum = calcMaxValueSum(0, _volume);
        cout << maxValSum << endl;

        for (int i = 0; i < _bookCount; i++) {
            delete[] _arrMaxVal[i];
        }

        delete[] _arrMaxVal;

        delete[] _arrVolume;
        delete[] _arrValue;
        delete[] _arrCount;

        delete[] _arrRemVol[MIN];
        delete[] _arrRemVol[MAX];
        delete[] _arrRemVal[MIN];
        delete[] _arrRemVal[MAX];

        delete[] _arrRemVol;
        delete[] _arrRemVal;

        caseIdx++;
    }

    return 0;
}

int calcMaxValueSum(int bookIdx, int remainVol) {
    if ((remainVol < _arrRemVol[MIN][bookIdx]) ||
        (remainVol > _arrRemVol[MAX][bookIdx]))
        return -999;
    else if (remainVol == _arrRemVol[MIN][bookIdx])
        return _arrRemVal[MIN][bookIdx];
    else if (remainVol == _arrRemVol[MAX][bookIdx])
        return _arrRemVal[MAX][bookIdx];
    else if (_arrMaxVal[bookIdx][remainVol] != 0)
        return _arrMaxVal[bookIdx][remainVol];

    int value = _arrValue[bookIdx];
    int volume = _arrVolume[bookIdx];
    int bookCount = _arrCount[bookIdx];

    int maxValSum = -999;

    for (int i = 0; i <= bookCount; i++) {
        int curRemain = remainVol - (volume * i);
        int curValSum = 0;

        if (curRemain < 0)
            break;
        else if (curRemain == 0)
            curValSum = (i * value);
        else if (bookIdx + 1 == _bookCount)
            continue;
        else {
            curValSum = calcMaxValueSum(bookIdx + 1, curRemain);

            if (curValSum < 0)
                continue;

            curValSum += (i * value);
        }

        if (curValSum > maxValSum)
            maxValSum = curValSum;
    }

    _arrMaxVal[bookIdx][remainVol] = maxValSum;

    return maxValSum;
}

    8년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.