Что-то не так с моим массивом идентификаторов?

Эта программа извлекает два столбца из файла input.txt, где первый столбец указывает значение объекта, а второй столбец представляет вес. Значения импортируются и помещаются в два массива: массив значений и массив весов. Расчеты ранца сделаны. Всего имеется 23 объекта, представленных рядами массивов. Мой код правильно вычисляет общее значение, которое хранится в рюкзаке, и будет печатать правильные идентификаторы, если введенная грузоподъемность равна 5, но для любого другого веса идентификаторы, содержащиеся в массиве идентификаторов, не являются правильными, но сумма значение распечатано. Вот мой код для обоих файлов, и если кто-нибудь сможет выяснить, как правильно сохранить и распечатать идентификаторы, хранящиеся в рюкзаке, пожалуйста, дайте мне знать.,,

файл 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;
}
Источник

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 от вашей старой попытки), а затем распечатайте элементы из списка в обратном порядке.

Источник
Другие вопросы по тегам