java - 带有零件集的背包递归解决方案

Question

我有java中背包问题的递归解决方案，这是我的代码:

public class OptimalIncome{
final static int length[] = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
final static int price[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
public static int totalLength = 9;

public static int bestCut(int i, int totalLength){
    if(i < 0){
        return 0;
    }
    else if(length[i] > totalLength){
        return bestCut(i - 1, totalLength);
    }
    else{
        return Math.max(bestCut(i - 1, totalLength), bestCut(i - 1, totalLength - length[i]) + price[i]);
    }
}

public static void main(String[] args){
    System.out.println("Given total rod length : " + totalLength);
    System.out.println("Maximum income         : " + bestCut(price.length-1, totalLength));
    System.out.println("Smaller part sets      : ");
}
}

它工作得很好，正如你所看到的，我想打印一组选择(较小的部分)。我怎样才能做到这一点？谢谢

Answer 1

我们开始:

导入java.util.ArrayList;导入java.util.List;

public class OptimalIncome {
    final static int length[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    final static int price[] = new int[] { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
    public static int totalLength = 9;
    static List<Integer> pickedObjects = new ArrayList<Integer>();
    public static int bestCut(int i, int totalLength) {
        if (i < 0) {
            return 0;
        } else if (length[i] > totalLength) {
            return bestCut(i - 1, totalLength);
        } else {
            return Math.max(bestCut(i - 1, totalLength),
                    bestCut(i - 1, totalLength - length[i]) + price[i]);
        }
    }

    public static void printSolution(int i,int totalLength){
        if(i < 0)
            return;
        else if(length[i]>totalLength){
            printSolution(i-1, totalLength);
        }else{
            int sol1 = bestCut(i-1,totalLength);
            int sol2 = bestCut(i - 1, totalLength - length[i]) + price[i];
            // check whether the optimal solution coming from picking the object or not .
            if(sol1>sol2){
                printSolution(i-1, totalLength);
            }else{

                pickedObjects.add(i);
                printSolution(i-1, totalLength - length[i]);
            }
        }
    }
    public static void main(String[] args) {
        System.out.println("Given total rod length : " + totalLength);
        System.out.println("Maximum income         : "
                + bestCut(price.length - 1, totalLength));
        System.out.println("Smaller part sets      : ");
        printSolution(price.length-1, totalLength);
        for (Integer i : pickedObjects) {
            System.out.println("picked object: "+ i +" length : "+ length[i]+ " price "+ price[i]);
        }
    }
}

我们只需要进行逆递归并检查您是否获得了构建输出的最佳解决方案。

尽管我认为您可能会在解决方案中添加一些内存，以便它足够快。希望对您有所帮助。