递归蛮力0-1背包 - 添加项目选择输出

Question

我正在练习递归算法，因为尽管我喜欢递归，但在进行“双重递归”时我仍然遇到麻烦。所以我创建了这个强力0-1 Knapsack算法，它将输出最终的权重和最佳值，而且它非常好，但是我认为只有当你知道哪些项目在这些数字后面时，信息才是相关的。不过，我被困在这里了。我想要优雅地做这件事，而不是创造一团乱七八糟的代码，也许我过分限制了我的想法，试图实现这个目标。我想我会在这里发布代码，看看有没有人有关于添加代码来输出选择的项目的一些漂亮的想法。这就是Java：

public class Knapsack { 

static int num_items = 4; 
static int weights[] = { 3, 5, 1, 4 }; 
static int benefit[] = { 2, 4, 3, 6 }; 
static int capacity = 10; 

static int new_sack[] = new int[num_items]; 
static int max_value = 0; 
static int weight = 0; 

// O(n2^n) brute force algorithm (i.e. check all combinations) : 
public static void findMaxValue(int n, int currentWeight, int currentValue) { 

    if ((n == 0) && (currentWeight <= capacity) && (currentValue > max_value)) { 
     max_value = currentValue; 
     weight = currentWeight; 

    } 

    if (n == 0) { 
     return; 
    } 

    findMaxValue(n - 1, currentWeight, currentValue); 
    findMaxValue(n - 1, currentWeight + weights[n - 1], currentValue + benefit[n - 1]); 

} 



public static void main(String[] args) { 

    findMaxValue(num_items, 0, 0); 

    System.out.println("The max value you can get is: " + max_value + " with weight: " + weight); 
    // System.out.println(Arrays.toString(new_sack)); 

} 

}

Answer 1

0-1背包算法的关键是找到，如果不包括或包括在一个较高的值背包结果的项目。你的代码不会比较这两种可能性。执行此操作的代码如下所示：

public int knapsack(int[] weights, int[] values, int n, int capacity) { 
    if (n == 0 || capacity == 0) 
    return 0; 

    if (weights[n-1] > capacity) // if item won't fit in knapsack 
    return knapsack(weights, values, n-1, capacity); // look at next item 

    // Compare if excluding or including item results in greater value 
    return max(
    knapsack(weights, values, n-1, capacity),    // exclude item 
    values[n] + knapsack(weights, values, n-1, capacity - weights[n-1])); // include item 
}