标签: knapsack-problem

我已经用Scala中的每个项目之一写了一个有界背包问题的答案,并尝试将其转换为Haskell,结果如下:

knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> Int -> [ ( Int, Int ) ]
knapsack xs [] _   = xs
knapsack xs ys max =
    foldr (maxOf) [ ] [ knapsack ( y : xs ) ( filter (y /=) ys ) max | y <- ys
        , weightOf( y : xs ) <= max ]

maxOf :: [ ( Int, Int ) ] -> [ ( Int, Int …

当有超过1个属性时,我遇到了解背包问题的问题.当有1个房产时,

我必须编写一个使用带有2个属性的背包算法的程序.老师告诉我们,它必须在一个3d数组中完成.错误的实现将导致O(2 ^ n)处理时间.我无法想象这样的阵列会是什么样子.

让我们说这是我的意见:

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

输出看起来像这样:

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

输出的解释:2组记录适合第1行输入:

(1) - 记录编号1和记录编号3 …

我发现了一篇文章:
使用F#中的memoization继续传递样式解决0-1背包问题

关于在F#中实现的背包问题.当我学习这门语言时,我发现这非常有趣,并试图对此进行一些研究.这是我制作的代码:

open System
open System.IO 
open System.Collections.Generic

let parseToTuple (line : string) =
    let parsedLine = line.Split(' ') |> Array.filter(not << String.IsNullOrWhiteSpace)         |> Array.map Int32.Parse
    (parsedLine.[0], parsedLine.[1])

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        if cache.ContainsKey(x)
            then cache.[x]
        else
            let res = f x
            cache.[x] <- res
            res

type Item =
    {
        Value : int
        Size  : int
    }  

type ContinuationBuilder() = 
    member b.Bind(x, f) = fun k -> x (fun x -> …

对于有界背包问题,假设每个项目的价值是一样的重量和所有的权重为正整数,我想知道如果有一个地方相比,项目个数n个人物品重量小的情况下,优化和背包的容量是所有物品重量的一半？例如,100k物品,每件物品重量限制为[1,10].

该算法应给出精确的解决方案.我知道O(n*W)时间和O(W)空间DP算法,但认为在这种情况下可能有更好的方法来解决它.提前致谢.

这是一个算法挑战,O(n*W)时间解决方案在功能上是正确的,但不够快(比所需的速度慢).我似乎无法找到任何关于这个问题的东西.输入是项目权重列表,所需输出是可以装入背包的项目的最大总值.

我想我的问题与背包问题的变种有关,但我不能真正想出一个解决方案:

假设您在五金店,需要购买21个螺丝.他们只提供袋装:

• 袋X - 16螺丝 - 每螺杆1.56美元 - 25美元总计
• 袋Y - 8螺丝 - 每螺杆2.25美元 - 18美元总计
• 袋Z - 4螺丝 - 每螺丝1.75美元 - 7美元总计

现在你必须弄清楚你应该购买哪些包以获得21螺丝(或更多!)以尽可能低的价格.

所以我得到的是一张包含所有行李的表格和一个用于定义所需金额的变量.因此,我需要的是一个带有包名和所需金额的表格.

不幸的是,sqlfiddle已经关闭..但至少这是示例数据:

declare @bags table (id int, qty int, price decimal(19,4))
insert into @bags values
 (10, 16, 25.00)
,(20, 8, 18.00)
,(30, 4, 7.00)

declare @ReqQty int = 21

我真的很感谢你的帮助!希望我们能够解决这个问题,因为我需要使用这个重要功能来定制我们公司的ERP系统.

先感谢您!

编辑:我读背包整个维基百科的文章,有这样说的: 溢出近似算法, 它可能会产生一个近似算法,我们可以稍微溢出允许的重量限制.您希望获得至少与给定界限B一样高的总值,但是您可以超过权重限制...... 目前,该近似算法的解决方案是未知的.

所以我似乎更好地使用贪心算法而不是发明轮子？;)

我正在编写一个程序,使用背包解决方案找到最佳的MLB阵容.为此,我传递了玩家数据,其中包含玩家计算的价值和工资.作为一个背包问题,工资将是我的"重量".

我的问题是无法选择球员,而是选择最佳阵容.我选择投手,中锋,一垒手,二垒手,三垒手,短暂停站和三名外野手.我能成功地做到这一点.我希望我的"体重"为36,000,但我目前只选择一个总共21,000的阵容.

这是我的背包代码:

CalculateLineUp.prototype.findOptimalLineUp = function(data, capacity) {
  var items = data.data;
  var idxItem   = 0,
      idxCapSpace = 0,
      idxPosition = 0,
      oldMax    = 0,
      newMax    = 0,
      numItems  = items.length,
      weightMatrix  = new Array(numItems+1),
      keepMatrix    = new Array(numItems+1),
      positionArray = new Array("P", "C", "1B", "2B", "3B", "SS", "OF", "OF", "OF"),
      solutionSet   = [];

  // Setup matrices
  for(idxItem = 0; idxItem < numItems + 1; idxItem++){
    weightMatrix[idxItem] = new Array(capacity+1);
    keepMatrix[idxItem]   = new Array(capacity+1);
  }

  // Build weightMatrix from [0][0] …

您将如何解决背包的这种变体？

您有 n 个对象 (x1,...xn)，每个对象都有成本 ci 和值 vi (1<=i<=n) 以及一个附加约束 X，它是所选项目值的下限。找到 x1,...,xn 的子集，使值至少为 X 的项目的成本最小化。

我试图通过动态编程来解决这个问题，我想到的是将常用的表修改为 K[n,c,X] ，其中 X 是我需要达到的最小值，但这似乎对我无济于事。有什么好主意吗？

首先,我是一个PHP新手...所以我仍然编程和理解PHP程序.那说,

我有一个存储在数据库中的数字(数量)的集合.

问题:使用PHP和mySQL,

1. 什么是将此信息从数据库中取出的最佳方法,以使金额与其交易ID相关联

2. 最重要的是,我需要在db中找到一组匹配的数字,等于29的总和.

以下是Transaction_tlb我的数据库的事务表mydb

    Transaction_ID |     Name         |       Date      | Amount
    ---------------|------------------|-----------------|------------ 
    11012          | Jonathan May     |   6/12/2016     |     84
    21012          | John Pedesta     |   6/12/2016     |     38
    31012          | Mary Johnson     |   1/01/2017     |     12
    41012          | John Johnson     |   8/01/2017     |     13
    51012          | Keith Jayron     |   8/01/2017     |     17
    61012          | Brenda Goldson   |   8/01/2017     |     2
    71012          | Joshua Traveen   |   8/01/2017     |     78
    81012          | Remy ma …

I have a problem which is similar to the Knapsack problem, more specifically the multidimensional variation.

I have a bunch of objects which all have a cost, a value, and a category. I need to the Knapsack optimisation for value under a maximum cost, but also have a specific number of objects in each category.

I have successfully implemented in C++ the original knapsack algorithm, without paying attention to the categories.

When I tried to add the categories, I …

input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]

output:
2  
// [[250, 175, 120], [150]]

我最初的印象是,这看起来非常类似于动态编程硬币更换/背包问题,但它不是硬币更换(这将要求最少数量的重量来制作精确数量),而且它不是背包(重量没有值,就像我可以有超过1背包).

这个问题有一个共同的名称/解决方案吗？