0/1背包算法

Question

我对这个问题有点困惑。作为算法帮助我找到最大的利润从袋。但是这个算法并没有告诉我我应该拿哪一个项目会让我的利润最大。例如
n=4项，背包的容量M=8，利润=[15,10,9,5]，重量分别为w=[1,5,3,4]，当我解决这个问题时，我得到最大的利润为29

这里是解决方案[http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf]

但是我想知道我应该选哪一个项目才能赚29英镑。我不想做所有的组合，因为如果有n个项目，分别有n个权重和n个利润，那么会有多少组合。所以我想知道这个算法或其他算法有没有什么解决方案，可以给我利润总额最大的项目。请帮帮我。等待答复！非常感谢。

Answer 1

0-1背包确实希望您称量所有可能的组合，因为与分数背包不同，分数背包中我们可以使用贪婪算法获得最大利润，空白空间会降低每磅（重量）负载的有效利润。在0-1背包中，当我们考虑是否在背包中包含一个项目时，我们必须将解决方案与包含问题的子问题进行比较，该子问题在我们做出选择之前排除了该项。

因此，解决方案运行O（nW），其中n是物品的数量，W是可以放入背包的物品的重量

希望它澄清！

Answer 2

如果您的问题仍然是“但我想知道我应该选择哪个项目”，那么下面是一个打印实际项目的实现：

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

public class Knapsack
{

    private int counter = 0;
    private int[] values, weights;
    public Knapsack(int[] vs, int[] ws)
    {
        values = vs;
        weights = ws;
    }

    public Bag knap(int n, int w)
    {
        counter++;
        Bag ret = new Bag();
        if (n == -1) {
            return ret;
        }

        ret = knap(n - 1, w);
        assert ret.totalWeight() <= w;
        if (weights[n] > w) {
            // This weight alone is larger than our quota. Can't add any more.
            return ret;
        }
        int val1 = ret.totalValue();
        int weight1 = ret.totalWeight();
        int remain = w - weight1;
        if (weights[n] <= remain)
        {
            // We have space for this item. Add to bag.
            ret.add(n, values[n], weights[n]);
            return ret;
        }
        int max = w - weights[n];
        ArrayList<Integer> nitems2 = new ArrayList<Integer>();
        Bag ret2 = knap(n - 1, w - weights[n]);
        ret2.add(n, values[n], weights[n]);
        int val2 = ret2.totalValue();
        int weight2 = ret2.totalWeight();
        if (val1 > val2) {
            return ret;
        } else {
            return ret2;
        }
    }

    public static void main(String[] args)
    {
        int[] values = {15, 10, 9, 5};
        int[] weights = {1, 5, 3, 4};
        int M = 8;

        Knapsack ks = new Knapsack(values, weights);
        Bag ret = ks.knap(values.length - 1, M);
        System.out.println("Total value=" + ret.totalValue() + ", weight=" +
                       ret.totalWeight());
        List<Integer> items = ret.bagItems();
        System.out.print("Items: ");
        for (int i: items) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

class Bag {
    private int weight;
    private int value;
    private ArrayList<Integer> items;
    public Bag()
    {
        weight = 0;
        value = 0;
        items = new ArrayList<Integer>();
    }

    public void add(int itemno, int v, int w)
    {
        items.add(itemno);
        weight += w;
        value += v;
    }

    public int totalWeight() { return weight; }
    public int totalValue() { return value; }
    public List<Integer> bagItems() { return items; }
}

Answer 3

动态编程：

对于0/1背包，您可以拿走整个物品，也可以完全离开。因此，您必须计算所有可能的解决方案，然后才能决定哪一个是最好的。

贪心法

在另一个背包问题中，你可以拿走一小部分物品，你可以按照成本来做，也就是说，拿最高成本的物品，装满你的背包，直到你的背包满了或者没有更多的物品，然后继续拿第二高成本的物品等等...