标签: knapsack-problem

当所有利润都等于 1 时，背包问题有一个变体。看起来它可以比经典离散 (0-1) 背包问题更快地解决，但是如何解决呢？贪婪算法会起作用吗（在每次迭代中将重量最小的物体放入背包中）？

我正在研究背包问题的DP解决方案。有了一个包含重量和价值的物品列表，我需要找到最大总价值小于某个预定义重量的物品。没什么特别的，就是0-1个背包。

我使用DP生成矩阵：

def getKnapsackTable(items, limit):
    matrix = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
    for j in xrange(1, len(items) + 1):
        item, wt, val = items[j-1]
        for w in xrange(1, limit + 1):
            if wt > w:
                matrix[j][w] = matrix[j-1][w]
            else:
                matrix[j][w] = max(matrix[j-1][w], matrix[j-1][w-wt] + val)

    return matrix

其中 items 是元组列表(name, weight, value)。现在有了 DP 矩阵，最大可能值就是右下位置的数字。我还可以回溯矩阵以找到提供最佳解决方案的项目列表。

def getItems(matrix, items):
    result = []
    I, j = len(matrix) - 1, len(matrix[0]) - …

我了解了基本的0-1背包问题及其解决方案。我试图通过 0-1 问题的变体进行推理，其中您不能从单个列表中选择任何项目组合，而是必须从许多不同项目集中分别选择一个项目。

例如，在我的问题中，项目列表如下所示：

食物

• 香蕉（重量9，价值10）
• 面包（重量3，价值25）
• 苹果（重量4，价值30）
• ...

衬衫

• T恤（重量2，价值20）
• 系扣衬衫（重量 3，价值 25）
• ...

裤子

• 卡其裤（重量4，价值30）
• 牛仔裤（重量2，价值30）
• ...

依此类推，问题要求您从食物中精确选择一件商品，从衬衫中选择一件商品，从裤子中选择一件商品，依此类推。

我认为有一个从 Rosetta 代码修改而来的强力解决方案，并且似乎可以工作（如下），但我无法弄清楚如何创建更有效的动态编程解决方案。谁能帮助或指出我正确的方向？我会很感激。

from itertools import product

def anycomb(item1, item2, item3, item4):
    return ( comb
             for comb in product(item1, item2, item3, item4)
             )

def totalvalue(comb):
    ' Totalise a particular combination of items'
    totwt = totval = 0
    for item, wt, val in comb:
        totwt  += wt
        totval += val
    return (totval, -totwt) …

我正在尝试为背包算法设计一个伪代码，其中可以多次选择单个项目。经典算法是

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i-1, w-wi))

为了满足要求，我修改为

k=1;
max = maximum(OPT(i-1, w))
while(OPT(i-1, w - k*wi) > 0) {
  maximum = max(maximum, k*vi + OPT(i-1, w - k*wi))
  k++
}
OPT(i, w) = maximum

这似乎是一个合适的解决方案吗？或者还有更好的解决方案吗？如果需要任何其他信息，请告诉我。其余保持不变，vi表示第i个元素的值，wi表示第i个元素的权重。

我有以下问题：

解决背包0-1问题（不是分数） 假设每个物体都有重量w1或w2（只有两个重量）。容量=W，算法必须运行在O(nlogn)上。

我尝试解决，贪心算法不行，动态规划算法是O(n*W)。

谁能给我提示。谢谢。

我有一组（多）正数，例如。{71.28, 82.62, 148.77, 85.05, 50.76, 103.41}。

我想找到给出最小总和大于或等于给定数字的子集。

例如。如果最小值为270，则结果为{148.77, 71.28, 50.76}，总和为270.81。

注意：我认为该解决方案可能比子集和更类似于背包。

是否有一种算法可以确定具有精确重量 W 的背包？即它就像普通的 0/1 背包问题，其中 n 个物品的重量为 w_i，价值为 v_i。最大化所有物品的价值，但是背包中物品的总重量需要正好有重量 W！

我知道“正常”的 0/1 背包算法，但这也可以返回重量更轻但价值更高的背包。我想找到最高值但精确的 W 重量。

这是我的 0/1 背包实现：

public class KnapSackTest {
    public static void main(String[] args) {
        int[] w = new int[] {4, 1, 5, 8, 3, 9, 2};  //weights
        int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values

        int n = w.length;
        int W = 15; // W (max weight)

        int[][] DP = new int[n+1][W+1];

        for(int i = 1; i …

实际上,我有一组与概率的对象,我想看看每个可能的一群人,在顺序的可能性有多大,他们是所有真正的假设他们是独立的-即以递减的顺序子集元素的乘积 - 或者如果概率相同则按长度顺序(使得(1,0.5)在(0.5)之后).

示例:如果我有[ 1, 0.5, 0.1 ]我想要的[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

从本质上讲,这意味着我想按顺序遍历一组元素的powerset,我可以相当容易地生成它,对它进行排序,并完成.然而,powersets变得非常快,我希望我通常会想要第一个子集中的一个,而我宁愿不生成数千个子集的列表,对它们进行排序,然后再也不会超过第三个子集.这就是python生成器希望挽救这一天的地方!

更正式的问题说明,我需要找到一种方法sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True),作为生成器,或以其他方式让我避免构建和排序整个列表.

我有理由相信这与背包问题以及子集产品问题有关,但我真的很难为它获得一个很好的算法,并且非常感谢帮助:-).这不是一个问题,因为它比在最坏的情况下构建+排序整个事情要慢(迭代一直到最后),它只需要更好的最佳情况(在前10%,比如说)性能.

因此,对于练习题,我们应该设计一个动态编程算法,它是0/1背包问题的变体......基本上每个项目来自4个不同的来源,并且该项目只能从其中一个来源获取. .

也就是说,

S1={(d_k, b_k) | 1 ? k ? n},
S2={(d_k, b_k) | n + 1 ? k ? 2n},
S3={(d_k, b_k) | 2n + 1 ? k ? 3n},
S4 = {(d_k, b_k) | 3n + 1 ? k ? 4n}

因为n = 10,如果你选择i = 16放,这意味着你不会选择6, 26 or 36...

你能帮助我解决这个问题并设计复发方程吗？

因此,我正在尝试生成一种算法,该算法将找到n项的最佳组合(在我的情况下为4),只能在背包中放置一次(0-1)并具有最大重量容量.可能更有效地概括,我想在我的背包中放置不超过四个独特的物品,以便它们的重量小于某个值W,同时最大化它们的总价值.我的第一次尝试和假设是将体积限制为4,所有项目体积为1,用于多维背包问题.但是我遇到了它不是0-1的问题(意思是否在袋子里).然后我尝试制作一个多维的0-1(有界)背包代码,但我无法添加音量限制以及0-1要求.如何编写0-1多维背包问题？或者我如何调整代码只保留一个V卷,所有项目卷为1？代码不一定是Java,但这是我到目前为止所拥有的.

背包:

package hu.pj.alg;

import hu.pj.obj.Item;
import java.util.*;

public class ZeroOneKnapsack {

    protected List<Item> itemList  = new ArrayList<Item>();
    protected int maxWeight        = 0;
    protected int solutionWeight   = 0;
    protected int profit           = 0;
    protected boolean calculated   = false;

    public ZeroOneKnapsack() {}

    public ZeroOneKnapsack(int _maxWeight) {
        setMaxWeight(_maxWeight);
    }

    public ZeroOneKnapsack(List<Item> _itemList) {
        setItemList(_itemList);
    }

    public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
        setItemList(_itemList);
        setMaxWeight(_maxWeight);
    }

    // calculte the solution of 0-1 knapsack problem with dynamic method:
    public List<Item> calcSolution() {
        int n = …