我的id数组有问题吗?

Question

该程序从input.txt文件中提取两列，其中第一列表示对象的值，第二列表示权重。这些值被导入并放入两个数组中:值数组和权重数组。然后进行背包计算。总共有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)，然后以相反的顺序从列表中打印项目