新手求助背包问题

Question

大家熟悉的背包问题 但是我的输出结果是
Enter the maximum weight: 10.0Enter the number of items to place in the Knapsack: 4Enter the weight: 7.0Enter the value : 42.0Enter the weight: 3.0Enter the value : 12.0Enter the weight: 4.0Enter the value : 40.0Enter the weight: 5.0Enter the value : 25.0Max Weight: 10.0Index: 0Weight: 7.0Value : 42.0Index: 1Weight: 3.0Value : 12.0Index: 2Weight: 4.0Value : 40.0Index: 3Weight: 5.0Value : 25.0The combination with the highest value and weight less than 10.0 is: 3
结果应该是23才对

Answer 1

这个是代码 如果还需要其他的我马上上传/**************************************************************************
 *  Compilation:  javac Knapsack.java
 *  Execution:    java Knapsack N W
 *
 *  Generates an instance of the 0/1 knapsack problem with N items
 *  and maximum weight W and solves it in time and space proportional
 *  to N * W using dynamic programming.
 */public class KnapsackCombination {    public static int[] combinations(KnapsackItems items) {
        int numberOfItems = items.getSize();
        int numberOfItemsToChoose = 1;
        int previousNumberOfItemsToChoose = 0;
        int startIndex = -1;
        int endIndex = numberOfItems;
        int depthOfRecursion = 0;
        double bestValue = 0;
        int[] bestCombinationIndices = new int[numberOfItemsToChoose];
        int[] testIndices = new int[numberOfItemsToChoose];
        bestCombinationIndices = getBestCombinationIndices(numberOfItems, numberOfItemsToChoose, startIndex, endIndex, depthOfRecursion, bestValue,                                                           testIndices, bestCombinationIndices, items);
        System.out.println(items.evaluate(bestCombinationIndices));        return bestCombinationIndices;    }
    private static int[] getBestCombinationIndices(int numItems, int numItemsToChoose, int startIndex, int endIndex, int depthOfRecursion, double bestValue,                                                   int[]testIndices, int[] bestIndices, KnapsackItems items) {        // Anchor Case: When the depth of recursion is equal to the number of total items minus 1 we know we have finished that test array.        if (depthOfRecursion == numItems - 1) {            return bestIndices;        }        // Inductive Case: Loop until our number of items to choose is equal to the number of recursive calls we have made.        else {
            for (int i = startIndex + 1; i < endIndex; i++) {                // Create a new array with adjusted size so that we can prevent going out of bounds, and counting zeros in the                // evaluate method that should not be included.                int[] tempTestArray = new int[depthOfRecursion + 1];                int[] tempBestArray = new int[depthOfRecursion + 1];                int[] lastCheckedIndices = new int[depthOfRecursion + 1];                assignArray(tempTestArray, testIndices);                testIndices = tempTestArray;                // Set the next index we need to test                testIndices[depthOfRecursion] = i;                    System.out.println(bestValue + "  " + items.evaluate(testIndices) + "  " + items.evaluate(bestIndices));             // If the value for the new array is better than that of the old one, get the indices for the new array                if (bestValue < items.evaluate(testIndices)) {                    assignArray(tempBestArray, testIndices);                    bestIndices = tempBestArray;                }
                testIndices = getBestCombinationIndices(numItems, numItemsToChoose, i, endIndex, depthOfRecursion + 1, bestValue,                                                        testIndices, bestIndices, items);
                // Increase the number of items to look at                if(numItemsToChoose == numItems - 1) {                    numItemsToChoose++;                }            }        }
        return bestIndices;    }    /*     * A method used to copy values from one array to another, mainly for increasing array size.     */    private static void assignArray(int[] arrayToCopyTo, int[] arrayToCopyFrom) {        if (arrayToCopyTo.length > arrayToCopyFrom.length) {            for (int i = 0; i < arrayToCopyTo.length - 1; i++) {                arrayToCopyTo[i] = arrayToCopyFrom[i];            }        }        else {            for (int i = 0; i < arrayToCopyTo.length; i++) {                arrayToCopyTo[i] = arrayToCopyFrom[i];            }        }    }   
}