获取背包中的对象列表

Question

我遇到了类似于 0-1 Knapsack 的问题。

我想做的修改是获取所选对象的列表而不是成本。我尝试使用以下代码：

public static int fillPackage(double weight,ArrayList<Item> item, int n) {
    //base case
    if(n == 0 || weight == 0)
        return 0;

    if(item.get(n - 1).getWeight() > weight)
        return fillPackage(weight, item, n - 1);    

    else {
        int include_cost = item.get(n - 1).getCost() + fillPackage((weight - item.get(n - 1).getWeight()), item, n - 1);
        int exclude_cost = fillPackage(weight, item, n - 1);
        if(include_cost > exclude_cost) {
            my_pack.add(item.get(n - 1));
            return include_cost;
        }
        else {
            return exclude_cost;
        }
    }   
}

此处my_pack是应该存储所选对象的ArrayList。但是，它也在存储其他对象。另外，我不能使用 DP table 方法，因为我的参数是 float.

my_pack.add() 行应该放在哪里？

Answer 1

问：

where should my_pack.add() line be put ?

答：

将 my_pack.add() 放到任何地方都无法获得正确的代码。

让我告诉你怎么做。你知道解决0-1 Knapsack的方法是：

best_cost = max(included_cost, excluded_cost)

所以同样，你应该这样想你的问题：

if included_cost > excluded_cost
    best_choice = included_best_choice + included_item
else
    best_choice = excluded_best_choice

我修改了你的代码，它可以正确解决你的问题（你可以编辑运行我的测试代码）。请参阅下面的代码。

有什么问题欢迎留言，我会尽快回复

import java.util.ArrayList;
import java.util.List;

public class Package {

    static List<Item> my_pack;

    public static int fillPackage(double weight, ArrayList<Item> item, List<Item> optimalChoice, int n){
        //base case
        if(n == 0 || weight == 0)
            return 0;

        if(item.get(n-1).getWeight() > weight) {
            List<Item> subOptimalChoice = new ArrayList<>();
            int optimalCost =fillPackage(weight, item, subOptimalChoice, n-1);
            optimalChoice.addAll(subOptimalChoice);
            return optimalCost;
        }
        else{
            List<Item> includeOptimalChoice = new ArrayList<>();
            List<Item> excludeOptimalChoice = new ArrayList<>();
            int include_cost = item.get(n-1).getCost() + fillPackage((weight-item.get(n-1).getWeight()), item, includeOptimalChoice, n-1);
            int exclude_cost = fillPackage(weight, item, excludeOptimalChoice, n-1);
            if(include_cost > exclude_cost){
                optimalChoice.addAll(includeOptimalChoice);
                optimalChoice.add(item.get(n - 1));
                return include_cost;
            }
            else{
                optimalChoice.addAll(excludeOptimalChoice);
                return exclude_cost;
            }
        }
    }

    public static void main(String args[]) {
        ArrayList<Item> itemList = new ArrayList<>();
        itemList.add(new Item(2, 1));
        itemList.add(new Item(5, 6));
        itemList.add(new Item(3, 2));
        itemList.add(new Item(4, 4));
        itemList.add(new Item(7, 7));

        printOptimalChoice(itemList, 9);
        printOptimalChoice(itemList, 10);
        printOptimalChoice(itemList, 11);
    }

    private static void printOptimalChoice(ArrayList<Item> itemList, double weight) {
        my_pack = new ArrayList<>();
        fillPackage(weight, itemList, my_pack, itemList.size());
        System.out.println("Best choice for weight: " + weight);
        for(int i = 0; i < my_pack.size(); i++) {
            System.out.println(my_pack.get(i));
        }
    }
}

我的测试输出：

Best choice for weight: 9.0
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}
Best choice for weight: 10.0
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}
Best choice for weight: 11.0
Item{weight=2.0, cost=1}
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}

Item.class代码：

class Item {
    private double weight;
    private int cost;

    public Item(double weight, int cost) {
        this.weight = weight;
        this.cost = cost;
    }

    @Override
    public String toString() {
        return "Item{" +
                "weight=" + weight +
                ", cost=" + cost +
                '}';
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    public int getCost() {
        return cost;
    }

    public void setCost(int cost) {
        this.cost = cost;
    }
}

获取背包中的对象列表

Getting object list in Knapsack

java

algorithm

arraylist

knapsack-problem

dynamic-programming