BOOKTHIEF 문제 질문입니다.

  • instigation
    instigation

    BOOKTHIEF

    문제의 테스트 케이스와 kriii님이 댓글 다신 테스트 케이스는 모두 잘 돌아가는데 제출하면 계속 오답이 뜹니다. 어떤 테스트 케이스에서 틀리는지 모르겠습니다. 도와주세요 ㅠ

    자루의 무게 v에 대해서 동적할당을 하여 문제를 풀었습니다.

    best(int v) : 크기 v인 자루로 얻을수 있는 최대 가치를 반환하는 함수

    • 책의 무게가 a1,a2,...,an이고 가치가 b1,b2,...,bn일 때 best(v)=max{best(v-a1)+b1,best(v-a2)+b2,...,best(v-an)+bn)}임을 이용합니다.

    cache[v][101] : best의 값을 저장합니다. 100번째에는 가치를, 0~99까지는 각 최선의 선택을 했을 경우에 훔치는 책들의 권수를 저장합니다.

    book[n][3] : 차례대로 크기,값어치,개수를 저장합니다.(문제의 순서)

    #include <stdio.h>
int n,book[100][3];
long int cache[10000][101];

long int best(int v)
{
    if(cache[v][100]!=-1)
        return cache[v][100];
    long int max=0,val,j=-1;
    for(int i=0;i<n;i++)
    {
        if(!(v>=book[i][0]&&(book[i][2]-cache[v-book[i][0]][i])>0))
            continue;
        val=cache[v-book[i][0]][100]+book[i][1];
        if(val>max){
            max=val;
            j=i;
        }
        if(val==max)
        {
            int maxn=0,valn=0;
            for(int k=0;k<n;k++)
            {
                maxn+=cache[v-book[j][0]][k];
                valn+=cache[v-book[i][0]][k];
            }
            if(maxn>valn){
                max=val;
                j=i;
            }
        }
    }
    if(j==-1)
        return 0;
    cache[v][100]=max;
    for(int i=0;i<n;i++){
        if(i!=j)
            cache[v][i]=cache[v-book[j][0]][i];
        else
            cache[v][i]=cache[v-book[j][0]][i]+1;
    }
    return max;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int v;
        long int Max=0;
        for(int i=0;i<100;i++)
            for(int j=0;j<3;j++)
                book[i][j]=0;
        //캐시초기화
        for(int i=0;i<=10000;i++){
            cache[i][100]=-1;
            for(int j=0;j<100;j++){
                cache[i][j]=0;
            }
        }
        cache[0][100]=0;
        scanf("%d %d",&n,&v);
        for(int i=0;i<n;i++)
            scanf("%d %d %d",&book[i][0],&book[i][1],&book[i][2]);
        for(int i=1;i<=v;i++){
            best(i);
            if(Max<best(i))
                Max=best(i);
        }
        printf("%ld\n",Max);
    }
    return 0;
}


    10년 전
2개의 댓글이 있습니다.
  • VOCList
    VOCList

    두 개의 자루부피 v1 < v2가 있습니다.
    v1에 대한 최적값을 구성하는 책의 권수가 (1, 1, 3) 과, (2, 1, 1)이 있다고 가정합시다. 이 때 만약 위 코드에서 (1, 1, 3)만을 기억한다면, v2에서 v1을 참고하여 자신의 테이블을 채울 때 (2, 1, 1) 구성에 책을 더하는 방법은 고려할 수 없게 됩니다.
    이 부분을 보강해야 할 것 같습니다.

    덧붙여 이 문제에서는 상관없는 부분이지만, long int 는 제 컴퓨터에선 4바이트형 정수로 나오네요. 만약 8바이트형 정수를 사용하고 싶으셨던 거라면 long long을 사용하시는 것이 나아보여용.


    10년 전 link
  • instigation
    instigation

    그렇군요.. 감사합니다.


    10년 전 link

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