배낭 동적 프로그래밍

Question

이것은 동적 프로그래밍이 필요한 일반적인 배낭 문제이며 항목 공급에 제약이 없습니다. 나는이 수업을 위해 수업을 진행 해왔고 몇 시간 동안 알고리즘을 가지고 놀려고 노력했지만 여전히 나는 그곳에 가지 못하고있다.

public static int fitBackPack(int[] W, int[] V, int T){ 
    int[] Opt = new int[T+1]; 
    Opt[0]=0; 
    for (int i=1; i<=T; i++){ 
     int localMax=0; 
     int globalMax=0; 
     for (int j=0; j<W.length; j++){ 
      if (W[j]<=i){ 
       localMax = (T%W[j]<=W[j]) ? V[j] : V[j]+Opt[T-W[j]]; 
       globalMax = (localMax>=globalMax) ? localMax : globalMax; 
      } 
     } 
     Opt[i]=globalMax; 
    } 
    //debugging purposes 
    for (int k=0; k<Opt.length; k++){ 
     System.out.println("Opt["+k+"] = "+Opt[k]); 
    } 
    return Opt[T]; 
} 

이 방법은 중량 각각 항목의 값과, 최대 가중치를 나타내는 정수 T를 들어, W 및 V의 정렬 된 배열을 가정한다. 내 산출물의 경우, T = 21까지의 모든 것이 작동하지만, 그 후에는 내가 원하는 바가 전혀없는 탐욕스러운 알고리즘처럼 작동하는 것 같습니다. 어떤 힌트를 주셔서 감사합니다, 감사합니다!

Answer 1

힌트 : (X %의 y를 < = Y) == 모든 이제 다음 테스트 케이스와 조건을 통해 진실의 표는이를 찾는 데 도움이됩니다

사실. 일반 용도 및 엣지 경우에 대한 자동화 된 테스트를 설정하는 것이 더 좋습니다.

Answer 2

알고리즘이 탐욕스러운 행동을하기 때문에, 문제는 아마도 localMax입니다 (탐욕 알고리즘은 가장 높은 지역 값을 찾습니다). 코드를 살펴보면 localMax이 잘못 된 것 같습니다. 힌트, Math.max() 기능을 참조하십시오.