PACKING 질문드릴께요~!!

  • kws4679
    kws4679

    PACKING을 풀던중에 궁금한게 있어서 질문드립니다!!

    하다가 잘 안되서 결국 책에있는방식으로 풀어서

    테스트를 통과하긴 했는데요 처음에는 이렇게 풀었습니다.

    PACKING 이전에 LIS 에서 설명했던대로

    완전탐색을 하면서 choices[101] 배열에 넣었습니다.

    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;
    vector<string> names,results;
    int volumes[101], desire[101], choices[101];
    int cache[101][1001];
    int n,w, counts=0;
    int desireSum(int index, int v, int count){
        if(index>=n) return 0;
        int& ret = cache[index][v];
        if(ret != -1) return ret;
        ret = desireSum(index+1, v, count);
        if(v+volumes[index] <= w){
            int cand = desireSum(index+1,v+volumes[index],count+1)+desire[index];
            if(ret < cand){
                choices[count] = index+1;
                ret = cand;
            }
        }
        return ret;
    }
    int main(){
        int c;
        scanf("%d", &c);
        while(c--){
            memset(volumes, 0, sizeof(volumes));
            memset(desire, 0, sizeof(desire));
            memset(cache, -1, sizeof(cache));
            memset(choices, 0, sizeof(choices));
            names = vector<string>();
            results = vector<string>();
            counts = 0;
            scanf("%d %d", &n, &w);
            string name;
            for(int i=0;i<n;++i) {
                cin >> name;
                scanf("%d %d", &volumes[i], &desire[i]);
                names.push_back(name);
            }
            int result = desireSum(0,0,0);
            for(int i=0;i<n;++i) if(choices[i]) counts++;
            printf("%d %d\n", result, counts);
            for(int i=0;i<n;++i) if(choices[i]) printf("%s\n", names[choices[i]-1].c_str());
        }
        return 0;
    }
    

    여기서 index 는 물건의 인덱스, v 는 부피, count 는 물건을 고른

    개수이므로, count번째에 index물건을 저장하는(골랐다면) 것이라고

    생각했는데 잘 안나오네요 ㅠㅠ 이런식으로 접근하면 안되는건가요?


    11년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    소스 코드 앞뒤에 빈줄을 하나씩 넣어주셔야 구문 강조가 잘 됩니다. 수정했으니 참고하세요.

    실제 답변은 아랫분이..


    11년 전 link
  • VOCList
    VOCList

    1
    3 2
    a 2 10
    b 1 1
    c 1 1

    위 예제를 살펴보세요.


    11년 전 link
  • VOCList
    VOCList

    @JongMan 글쓰기시 아래에 나오는 신텍스 하일라이팅 안내문 변경하는게 좋지 않을까요. 거기 예제도 앞뒤로 빈 줄이 없어서...


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