我的id数组有什么问题吗？ [英] Is there something wrong with my id array?

问题描述

该程序从input.txt文件中拉出两列，第一列表示对象的值，第二列表示权重。这些值被导入并放置在两个数组中：值数组和权重数组。然后进行背包计算。总共有23个对象由数组的行表示。我的代码正确地计算了背包中保存的总值，并且如果输入的权重容量为5，则打印出正确的ID，但是对于id列表中保存的ID是不正确的，但是对于任何其他权重，打印的价值是。这是我的两个文件的代码，如果任何人能够弄清楚如何正确保存和打印背包中的ID，请让我知道。 。 。

This program pulls two columns from the input.txt file where the first column indicates the value of the object, and the second column represents the weight. The values are imported and placed into two arrays: the value array and the weight array. The knapsack calculations are then made. There are 23 objects in total represented by the rows of the arrays. My code correctly calculates the total value that is being held in the knapsack, and will print out the correct IDs if the weight capacity entered is 5, but for any other weight the IDs being held in the id array are not correct, but the total value printed out is. Here is my code for both files, and if anyone is able to figure out how to correctly save and print the IDs being held in the knapsack please let me know . . .

input.txt文件：

input.txt file:

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文件：

knapsack.java file:

//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;
}

推荐答案

在 id 数组中有缺陷。当您执行 id [track ++] = i; 时，您还不知道是否我将在你的最终解决方案由于嵌套循环，您甚至可以多次添加 i 。这反过来可能导致数组溢出一个 java.lang.ArrayIndexOutOfBoundsException：23 （最大容量为12及以上）

Your way of recording your solution in the id array is flawed. At the time you do id[track++] = i;, you don’t yet know whether i will be in your final solution. Because of the nested loops you may even add i more than once. This in turn may lead to overflowing the array with a java.lang.ArrayIndexOutOfBoundsException: 23 (this happens for max capacity 12 and above).

我建议不要使用 id ，解决方案完成后，您可以通过 K 数组（通过Java命名约定，它应该是一个小的 k ）。它拥有您需要查找哪些对象包含在最大值中的所有信息。

I suggest instead of using id, after your solution is complete you track your way backward through the K array (by Java naming conventions, it should be a small k). It holds all the information you need to find out which objects were included in the maximum value.

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];
            }
        }
    }
}

以上打印对象向后。示例运行：

The above prints the objects backward. Example run:

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 从您的旧尝试），然后以相反的顺序从列表中打印项目。

If you want the objects in forward order, inside the for loop put them into a list (you may for instance use id from your old attempt), and then print the items from the list in opposite order.

这篇关于我的id数组有什么问题吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！