标签: knapsack-problem

我知道这Knapsack是NP完全的,而DP可以解决.他们说DP解决方案是pseudo-polynomial,因为它在"输入长度"(即编码输入所需的位数)中是指数的.不幸的是我没有得到它.有人能pseudo-polynomial慢慢向我解释那件事吗？

标准的0/1背包要求每件物品的重量独立于其他物品.然后DP是解决方案的有效算法.但是现在我遇到了类似但是这个问题的扩展,那个

新物品的重量取决于背包中已有的物品.

例如,我们有5个项目a,b,c,d和e体重w_a,... w_e.项目b并c具有重量依赖性.

当b已经在背包,物品的重量c会更小比w_c,因为它可以共享一些空间b,即weight(b&c) < w_b + w_c.对称地,当c已经在背包中时,重量b将小于w_b.

这种不确定性导致原始DP算法失败,因为它取决于先前迭代的正确性,现在可能无法纠正.我已经阅读了一些关于背包的论文,但是它们要么具有利润的依赖性(二次背包问题),要么具有随机分布的随机分布(随机背包问题).我也知道前面的问题1/0带有加权边缘的背包变化,但是只有一个非常通用的答案,并没有回答这个背包的名称是什么.

一个现有解决方案

我还在一篇关于DBMS优化的论文中阅读了一个近似的解决方案group the related items as one combined item for knapsack.如果使用这种技术进入我们的例子中,在背包的物品会a,bc,d,e,因此有这四个项目中的任何两者之间没有更多的依赖关系.然而,很容易构造一个没有得到最佳结果的例子,比如何时an …

有一个数字列表.

该列表将分为2个相等大小的列表,总和之间的差异最小.必须打印总和.

#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27

在某些情况下,以下代码算法是否存在错误？

我如何优化和/或pythonize这个？

def make_teams(que):
    que.sort()
    if len(que)%2: que.insert(0,0)
    t1,t2 = [],[]
    while que:
    val = (que.pop(), que.pop())
    if sum(t1)>sum(t2):
        t2.append(val[0])
        t1.append(val[1])
    else:
        t1.append(val[0])
        t2.append(val[1])
    print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"

问题来自http://www.codechef.com/problems/TEAMSEL/

我有一个代码,通过背包算法计算最佳值(bin packing NP-hard problem):

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for ( int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

另外,我需要显示包含在内的元素.我想创建一个数组,添加一个元素.所以问题在于添加这个添加的步骤,或者可能还有其他更有效的方法吗？

问题:我希望能够了解为我提供最佳解决方案的项目,而不仅仅是最佳解决方案的价值.

PS.对不起我的英语,这不是我的母语.

如果存在多个约束(例如,体积限制和重量限制,每个项目的体积和重量都不相关),我们会得到多重约束的背包问题,多维背包问题或者m - 三维背包问题.

如何以最优化的方式对其进行编码？那么,人们可以开发一种强力递归解决方案.可能是分支和绑定..但基本上它是指数大部分时间,直到你做某种记忆或使用动态编程,如果做得不好再次需要大量的内存.

我面临的问题是这个

我有我的背包功能KnapSack(容量,价值,i)而不是常见的KnapSack(容量,i),因为我对这两者都有上限.任何人都可以指导我吗？或提供合适的资源来解决相当大的n的这些问题

或者这个NP是完整的吗？

谢谢

在一个背包的情况下,用于最佳地填充背包的动态编程算法很好地工作.但是,是否有一种有效的已知算法可以最佳地填充2个背包(容量可能不相等)？

我尝试了以下两种方法,但它们都不正确.

1. 首先使用原始DP算法填充第一个背包,填充一个背包,然后填充另一个背包.
2. 首先填充尺寸为W1 + W2的背包,然后将溶液分成两个溶液(其中W1和W2是两个背包的容量).

问题陈述(另见维基百科的背包问题):

1. 我们必须用一组物品(每个物品具有重量和值)填充背包,以便最大化我们可以从物品获得的值,同时总重量小于或等于背包尺寸.

2. 我们不能多次使用一个项目.

3. 我们不能使用项目的一部分.我们不能把一个项目的一小部分.(每个项目必须完全包含或不包括在内).

我发现这个代码使用强力机制来解决背包问题(这主要是为了学习,所以不需要指出动态更有效).我得到了代码工作,并了解其中的大部分内容.最.这是问题:

我注意到这两个条件,我不知道它们是如何工作的以及为什么它们在代码中 - 我知道它们是至关重要的,因为我所做的任何改变都会导致算法产生错误的结果:

// if bit not included then skip
if (((i >> j) & 1) != 1) continue;

// if bit match then add
if (((bestPosition >> j) & 1) == 1)
{
    include.Add(Items[j]);
}

这是整个班级,以及我从主要方式调用它的方式:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnapSack2
{
    class BruteForce
    {
        public double Capacity { get; set; }
        public Item[] Items { get; set; }

        public Data Run()
        {
            int bestValue = 0;
            int bestPosition = 0;
            int size …

我在Haskell中编写了0-1背包问题.到目前为止,我对于懒惰和普遍性水平感到自豪.

我首先提供了创建和处理惰性2d矩阵的函数.

mkList f = map f [0..]
mkTable f = mkList (\i -> mkList (\j -> f i j))

tableIndex table i j = table !! i !! j

然后我为一个给定的背包问题制作一个特定的表格

knapsackTable = mkTable f
    where f 0 _ = 0
          f _ 0 = 0
          f i j | ws!!i > j = leaveI
                | otherwise = max takeI leaveI
              where takeI  = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i
                    leaveI = tableIndex knapsackTable (i-1) j

-- weight …

SPOILERS:我正在http://www.spoj.pl/problems/KNAPSACK/上工作,所以如果你不想为你破坏可能的解决方案,请不要偷看.

样板:

import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)

main = interact knapsackStr

knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
  where [capacity, numItems] = map read . words $ head ls
        ls = lines str
        items = map (makeItem . words) $ take numItems $ tail ls

设置舞台的一些类型和帮助:

type Item = (Weight, Value)
type Weight = Int
type Value = Int

weight :: Item -> Weight
weight = fst

value …

这是我的任务

背包问题是计算机科学的经典之作.在其最简单的形式中,它涉及尝试将不同重量的物品装入背包中,以使背包最终具有指定的总重量.您不需要适合所有项目.例如,假设您希望您的背包重量恰好为20磅,并且您有五件物品,重量为11,8,7,6和5磅.对于少量物品,人类通过检查很好地解决了这个问题.所以你可能会发现,只有8,7和5种项目的组合总计达20个.

我真的不知道从哪里开始编写这个算法.应用于阶乘和三角数时,我理解递归.但是我现在迷路了.