KNAPSACK 점화식.. 이거 두개가 차이가 있을까요?

  • skan1543
    skan1543 
            for(int i=1;i<=n;i++)
        {
            if(D[money[i]]<value[i]) D[money[i]]=value[i];
            for(int j=0;j<=m-money[i];j++)
            {
                if(D[j]!=0 && D[j+money[i]]<D[j]+value[i])
                    D[j+money[i]]=D[j]+value[i];
            }
        }

    이렇게 점화식을 세워서 해봤는데, 계속 오답이 뜨길래요..

        for(int i=1;i<=n;i++){
            for(int j=0;j<=m-money[i];j++)
                if(D[j+money[i]]<D[j]+value[i]){ D[j+money[i]]=D[j]+value[i];}
        }

    로 간단하게 바꿔주니 정답이 뜨더라구요..
    위에 처럼 풀어도 상관없지 않나요?
    반례가 있을ㅈ지요.. ㅠㅠㅠㅠ

    문제는 SUSHI 입니다!!


    8년 전
2개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    첫 코드에서 메뉴가 예산을 초과할 때 (money[i] > m) 계산 후 D 배열을 m까지만 초기화 헀다면 다음 테스트 케이스 계산시 틀릴 수도 있겠네요


    8년 전 link
  • skan1543
    skan1543

    헉..... 그렇군요 ...


    8년 전 link

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