색인에 문제가 있습니다.

Question

최대 가치 배낭 알고리즘을 쓰고 있습니다. 값과 비용이있는 항목이있는 배낭 개체가 필요합니다. 최대 값을 계산하기위한 2D 배열을 선언합니다. 기본 케이스의 경우 0 행 값과 0 열 값을 0으로 설정했습니다. 배낭에서 항목을 가져올 때 문제가 발생합니다. 0 번 항목을 가져올 때 첫 번째 항목을 실제로 잡아 내고 있기 때문에 문제가 발생합니다. 결과적으로 2D 배열에서 잘못된 값을 얻게됩니다. 누군가 내 코드를 확인하고 내가 누락 된 부분을 볼 수 있습니까?

public static double MaximumKnapsack(Knapsack knapsack) { 
    int numItems = knapsack.getNumOfItems(); 
    int budget = (int) knapsack.getBudget(); 
    double[][] DP = new double[numItems+1][budget+1]; 

    boolean taken = false; 
    for (int i = 0; i < numItems + 1; i++) { 
     for (int b = 0; b < budget + 1; b++) { 
      if (i == 0 || b == 0) { 
       DP[i][b] = 0; 
      } 
      else 
      { 
       Item item = knapsack.getItem(i); 
       if (item.getCost() > b) { 
        DP[i][b] = DP[i-1][b]; 
       } 
       else 
       { 
        DP[i][b] = Math.max(DP[i-1][b-(int) item.getCost()] + item.getValue(), 
             DP[i-1][b]); 
        if (DP[i][b] == DP[i-1][b-(int) item.getCost()] + item.getValue() && item.getCost() != 0.0) { 
         taken = true; 
        } 
       } 
      } 
     } 
     taken = false; 
    } 
    return DP[numItems][budget]; 
} 

Answer 1

내가 루프 내가 함께 시작됩니다 beacuse 문제가

Item item = knapsack.getItem(i); 

에 생각 = 1. 당신은 사용해야

Item item = knapsack.getItem(i-1);