Unbounded Knapsack Problem 관련 질문입니다.

  • canuyes
    canuyes

    안녕하세요.
    혼자 알고리즘을 공부중인 학생입니다.
    Unbounded Knapsack Problem(이하 UKP)를
    공부하던 중 모르는 것이 생겨 질문 올립니다.

    설명에 앞서 질문을 요약하자면,
    UKP를 2D array가 아닌 1D array를 사용하여 푸는 방법을 알고 싶습니다.

    그간 책도 보고 문제도 풀면서 knapsack problem을
    2D array로 푸는 방법은 알고 있습니다.
    (보통, "cache[x][P] : x번째 물건까지 사용하여 P원 이하로 가방을 쌀때, 최대 가치" 로 설정하여 풀어왔습니다.)
    bounded knapsack, 0-1 knapsack problem에서 캐시의 크기를
    (물건 수*가능 무게)로 설정하는 것에서
    (2*가능 무게)크기의 캐시로 설정하여 줄이는 방법도 배웠습니다.
    이전 질문 링크

    UKP에서는 1D array면 충분하다는 글을 읽었습니다.
    이것은 어떻게 구현해야 할까요?

    2012 ACM south east regional A번문제:candy store
    에 적용시켜 풀어보고자 아래와 같은 코드를 만들었습니다.

    #include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
struct CANDY{int cal,pri;};
int N,M;
double temp;
CANDY candy[5000];
vector<int> answer;
int cache[10001]={0,};
int bigger(int A,int B){if(A>B){return A;}return B;}
int compar(const void* A,const void* B){return ((CANDY*)A)->pri-((CANDY*)B)->pri;}
int mkANS(int P){
    int i,j;
    cache[0]=0;
    for(i=0;i<N;i++){
                     for(j=candy[i].pri;j<=P;j++){
                                                  cache[j]=bigger(cache[j],cache[j-candy[i].pri]+candy[i].cal);
    }}
    return cache[P];
}
int main(void){
    while(1){
             cin>>N>>temp;M=(int)(temp*100);
             if(N==0&&M==0){break;}
             for(int i=0;i<N;i++){cin>>candy[i].cal>>temp;candy[i].pri=(int)(temp*100);}
             qsort(candy,N,sizeof(CANDY),compar);
             memset(cache,0,sizeof(int)*(M+1));
             answer.push_back(mkANS(M));
    }
    for(int i=0;i<answer.size();i++){cout<<answer[i]<<endl;}
    system("PAUSE");
    return 0;
}

    그런데, 자꾸 WA를 뱉네요...
    2일째 부족한 머리탓에 고민중인데..이거 어떻게 해야할까요?
    ACM에서 공개한 채점데이터 링크 달아놓습니다.
    답변 기다립니다.^^

    인풋
    아웃풋


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

    우선 pause를 넣고 하신 것은 아니죠? ^^; 입력을 정수로 전환하는 과정에서 문제가 좀 보입니다. 0.29같은 숫자는 정확하게 실수로 표현될 수 없기 때문에, 0.289999999.. 식으로 내부적으로 표현될 수 있습니다. 이걸 100곱해서 곧장 정수로 내림하시면 28이 되어버리는 수가!! 예를 들어 제 컴퓨터에서는 다음 입력에 대한 정답이 잘못 나오더군요.

    1 0.28
100 0.29
0 0


    11년 전 link
  • wookayin
    wookayin

    틀린 이유는 위에 JongMan님이 설명해 주신거 같고 나머지는 맞는거 같네요.. 그 외 몇 가지 조언을 더 드리자면

    • ICPC 문제에서 답을 answer 등에 저장할 필요는 없고 그냥 그때그때 찍어주면 됩니다.
    • 정렬은 굳이 할 필요 없습니다.
    • qsort 같은건 안 쓰는게 좋습니다. std::sort 를 사용하세요.
    • bigger 같은 거 만들어 쓰기보단 이미 내장된 std::max 등을 쓰시면 좋습니다.

    참고하시라고 예전에 제가 짰던 소스를 첨부해 드립니다 :)

    http://ideone.com/fyXVYa


    11년 전 link
  • Baekjoon
    Baekjoon

    cache[j]=bigger(cache[j],cache[j-candy[i].pri]+candy[i].cal);

    이 부분에서 cache[j-candy[i].pri]의 값이 0인 경우는 원래 만들 수 없는 가격이기 때문에, 이용하면 안됩니다.

    그런데, 이 문제는 만들 수 있는 가장 큰 칼로리를 구하는 문제라서 저 값을 이용해도 정답은 나올 것 같네요.

    이와 비슷한 다른 문제를 풀 때는 저런 경우를 체크해야 할 것 같습니다.


    11년 전 link
  • canuyes
    canuyes

    감사합니다!
    조언대로 잘 해결되었습니다!


    11년 전 link

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