Problème avec les indices

Question

Je suis en train d'écrire un algorithme Knapsack Maximum Value. Il prend dans un objet Knapsack avec des éléments qui ont une valeur et un coût. Je déclare un tableau 2D pour calculer la valeur max. Pour les cas de base, j'ai mis les valeurs des lignes zéro à 0 et les valeurs des colonnes zéro à 0. Je rencontre des problèmes lorsque je prends un objet dans le sac parce que quand je veux saisir l'élément zéro, je sais vraiment le premier élément dans le sac à dos et je reçois par conséquent les mauvaises valeurs dans le tableau 2D. Quelqu'un peut-il vérifier mon code et voir ce qui me manque?

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

Je pense que le problème est dans

Item item = knapsack.getItem(i); 

beacuse votre boucle commence par i = 1. Vous devez utiliser:

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