私のid配列に何か問題がありますか？

Question

このプログラムはinput.txtファイルから2つの列を取り出します。最初の列はオブジェクトの値を示し、2番目の列は重みを表します。値はインポートされ、値配列と重み配列の2つの配列に配置されます。次に、ナップザック計算が行われる。配列の行によって表される合計で23のオブジェクトがあります。私のコードは正しくナップザックに保持されている合計値を計算し、入力された重量容量が5であれば正しいIDを出力しますが、ID配列に保持されているIDは正しくありませんが、値は印刷されます。ここでは両方のファイルのための私のコードは、誰が正しい保存し、ナップザックに保持されているIDを印刷する方法を把握することができる場合は私に教えてください。 。 。

INPUT.TXTファイル：

17 5 
12 8 
15 22 
17 11 
33 21 
43 15 
15 4 
44 35 
23 19 
10 23 
55 39 
8 6 
21 9 
20 28 
20 13 
45 29 
18 16 
21 19 
68 55 
10 16 
33 54 
3 1 
5 9 

knapsack.javaファイル：

//We did borrow concepts from: 

// http://www.sanfoundry.com/java-program-solve-knapsack-problem-using-dp/

import java.util.Scanner; 
import java.util.*; 
import java.lang.*; 
import java.io.*; 

public class knapsack 
{ 
    static int max(int a, int b) 
    { 
     if(a > b) 
     { 
      //System.out.println(a); 
      return a; 
     } 
     else 
      //System.out.println(b); 
      return b; 
    } 
    static int knapSack(int maxCapacity, int weight[], int value[], int n) 
    { 
     int track = 0; 
     int i, w; 
     int foo1 = 0; 
     int foo2 = 0; 
     K = new int[n+1][maxCapacity+1]; 

     // Build table K[][] in bottom up manner 
     for (i = 0; i <= n; i++) 
     { 
      for (w = 0; w <= maxCapacity; w++) 
      { 
       if (i==0 || w==0) 
       K[i][w] = 0; 
       else if (weight[i-1] <= w) 
      { 
       //K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w]); 
       if(value[i-1] + K[i-1][w-weight[i-1]] > K[i-1][w]) 
       { 
        K[i][w] = value[i-1] + K[i-1][w-weight[i-1]]; 
        //System.out.println("A: "+i); 

       } 
       else 
       { 
        K[i][w] = K[i-1][w]; 
        id[track++] = i; 
        //System.out.println("B: "+i); 
       } 

      } 
      else 
      { 
       K[i][w] = K[i-1][w]; 

      } 

     } 
     //System.out.println(K[foo1][foo2]); 
    } 

    return K[n][maxCapacity]; 
} 

public static void main(String args[])throws java.io.FileNotFoundException 
{ 
    Scanner sc = new Scanner(System.in); 
    int n = 23; 
    File file = new File("input.txt"); 
    Scanner scanner = new Scanner(file); 
    id = new Integer [n]; 
    //knapval = new int[n]; 
    //knapweight = new int [n]; 
    int []value = new int[n]; 
    int []weight = new int[n]; 
    for(int i=0; i<n; i++) 
    { 
     value[i] = scanner.nextInt(); 
     weight[i] = scanner.nextInt(); 

    } 

    System.out.println("Enter the maximum capacity: "); 
    int maxCapacity = sc.nextInt(); 
    System.out.println("The maximum value that can be put in a knapsack with a weight capacity of "+maxCapacity+" is: " + knapSack(maxCapacity, weight, value, n)); 
    System.out.println(); 
    System.out.println("IDs Of Objects Held In Knapsack: "); 
    //System.out.println(); 
    for(int z = 0; z < n && id[z] != null; z++) 
    { 
     System.out.println(id[z]); 
    } 
    if(id[0] == null) 
     System.out.println("All objects are too heavy, knapsack is empty."); 
    sc.close(); 
    scanner.close(); 


} 
protected static Integer [] id; 
protected static int [][]K; 
} 

Answer 1

id配列にあなたのソリューションを記録するあなたの方法は、欠陥があります。 id[track++] = i;を実行しているときに、iが最終的な解決策になるかどうかはまだ分かりません。ネストされたループのため、iを複数回追加することさえできます。これは、java.lang.ArrayIndexOutOfBoundsException: 23（これは最大容量12以上の場合に発生します）でアレイがオーバーフローする可能性があります。

idの代わりに、解決策が完了した後で、K配列を逆方向に追跡します（Java命名規則により、k）。これは、どのオブジェクトが最大値に含まれていたかを調べるために必要なすべての情報を保持します。

private static void printKnapsack(int maxCapacity, int weight[], int value[], int n) { 
    if (K[n][maxCapacity] == 0) { 
     System.out.println("No objects in knapsack"); 
    } else { 
     int w = maxCapacity; 
     for (int i = n; i > 0; i--) { 
      if (K[i][w] > K[i - 1][w]) { // increased value from object i - 1 
       System.out.format("ID %2d value %2d weight %2d%n", i, value[i - 1], weight[i - 1]); 
       // check that value in K agrees with value[i - 1] 
       assert K[i - 1][w - weight[i - 1]] + value[i - 1] == K[i][w]; 
       w -= weight[i - 1]; 
      } 
     } 
    } 
} 

上記は、オブジェクトを後方に印刷します。例を実行：

Enter the maximum capacity: 
13 
The maximum value that can be put in a knapsack with a weight capacity of 13 is: 36 

ID 13 value 21 weight 9 
ID 7 value 15 weight 4 

あなたは前方の順序でオブジェクトを使用する場合は、forループ内では、（あなたは、例えば古い試みからidを使用することができます）、リストに入れ、その後で、リストから項目を印刷します反対の順序。