0/1背包算法

Question

我在这个问题中有点困惑，这个算法帮助我从袋子.But中找到最大利润这个算法没有告诉我应该拿哪一件东西，这将使我的利润最大.As示例

n=4项、背包容量M=8、profit=15,10,9,5和重量分别为w=1,5,3,4时，我得到的最大利润为29

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

我不想做所有的组合，因为如果有n个项目，分别有N个重量和利润，那么会有多少个组合。所以我想知道对于这个算法或者其他算法，有没有什么解决方案，可以给出利润总和最大的项目。请帮帮我。正在等待回复！谢谢

Answer 1

动态编程：

对于0/1背包的

，您可以选择整个项目，也可以完全放弃它。因此，在决定哪一个是最好的之前，你必须计算所有可能的解决方案。

贪婪的方法

在另一个背包问题中，你可以取物品的一小部分，你可以按成本计算，即取最高成本的物品，装满你的背包，直到你的背包装满或没有更多的物品，然后转移到第二昂贵的物品，依此类推...

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背包确实想要你权衡所有可能的组合，因为在分数背包中，我们可以使用贪婪算法来获得最大利润，而空白空间降低了负载的每磅(重量)的有效利润。在0-1背包中，当我们考虑是否在背包中包含一个项目时，我们必须比较包含该项目的子问题的解与排除该项目的子问题的解，然后才能做出选择。

因此，解决方案运行O(nW)，其中n是项目的数量，W是可以放入背包中的项目的权重

希望它能澄清！