标签: knapsack-problem

我一直在使用这种动态编程变体来解决背包问题:

KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)


def dynamic_programming_knapsack(problem)
  num_items = problem.items.size
  items = problem.items
  max_cost = problem.max_cost

  cost_matrix = zeros(num_items, max_cost+1)

  num_items.times do |i|
    (max_cost + 1).times do |j|
      if(items[i].cost > j)
        cost_matrix[i][j] = cost_matrix[i-1][j]
      else
        cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
      end
    end
  end

  cost_matrix
end

def get_used_items(problem, cost_matrix)
  i = cost_matrix.size - 1
  currentCost = cost_matrix[0].size - 1
  marked = Array.new(cost_matrix.size, 0) 

  while(i >= 0 && currentCost >= 0)
    if(i == 0 && cost_matrix[i][currentCost] …

假设你是一个小偷,你入侵了一所房子.你在里面找到了以下物品:

一个重3磅的花瓶,价值50美元.
一块重6磅的银块,价值30美元.
一幅重4磅,价值40美元的画作.
重量为5磅,价值10美元的镜子.

这个尺寸为10磅的背包问题的解决方案是90美元.

由动态编程制成的表格是: -

现在我想知道我使用这张表放入麻袋的哪些元素然后如何回溯？

我试图解决这个问题,我想知道是否有已知的现有算法/解决方案来解决这个问题.

问题:

我有n个袋子和n个物品(可以是相同或不同的重量)来装入这些袋子.这些袋中的每一个都具有一定的重量限制,并且需要将n个物品放入这些袋中,使得我可以使用每个袋中的最大空间.

袋子大小相同.还想知道如何解决不同尺寸的包袋.

我读过的大部分解决方案都试图解决一个重量和价值都在0/1的背包.我应该考虑重量和价值吗？我是在正确的轨道上吗？

这不是一个家庭作业问题.

在Stack Overflow上显然无法将其称为问题,但我目前正在尝试了解如何在背包问题中以项目组的形式集成约束.在这种情况下,我的数学技能被证明是相当有限的,但我非常积极地使这项工作按预期进行,并弄清楚每个方面的作用(按顺序,因为事情在工作时更有意义).

话虽如此,我已经在Rosetta Code中找到了一个非常漂亮的实现,并清理了变量名称,以帮助自己从一个非常基本的角度更好地理解这一点.

不幸的是,我很难理解如何应用这个逻辑来包含项目组.我的目的是建立幻想团队,为每个玩家提供我自己的价值和体重(积分/工资)但没有团体(在我的情况下的职位)我无法这样做.

有人能指出我正确的方向吗？我正在审查其他语言的代码示例以及整个问题的其他描述,但我希望通过任何可能的方式实现这些组.

<?php

function knapSolveFast2($itemWeight, $itemValue, $i, $availWeight, &$memoItems, &$pickedItems)
{
    global $numcalls;
    $numcalls++;

    // Return memo if we have one
    if (isset($memoItems[$i][$availWeight]))
    {
        return array( $memoItems[$i][$availWeight], $memoItems['picked'][$i][$availWeight] );
    }
    else
    {
        // At end of decision branch
        if ($i == 0)
        {
            if ($itemWeight[$i] <= $availWeight)
            { // Will this item fit?
                $memoItems[$i][$availWeight] = $itemValue[$i]; // Memo this item
                $memoItems['picked'][$i][$availWeight] = array($i); // and the picked item
                return array($itemValue[$i],array($i)); // Return the value …

关于背包问题的维基百科文章包含三种类型的列表:

1. 1-0(一种类型)

2. 有界(一种类型的几个项目)

3. 无界限(无限数量的项目)

本文包含针对1.和3.类型问题的DP方法,但没有针对2的解决方案.

如何描述用于求解的动态编程算法？

我是一个新的动态编程,并在SPOJ (http://www.spoj.pl/problems/KNAPSACK/)尝试了整数背包问题.但是,对于给定的测试用例,我的解决方案是没有给出正确的输出.如果您能建议我的以下实施是否正确,我将感谢您.请注意,该变量back用于回溯,我不知道该怎么做.我希望能帮助你实现回溯.谢谢.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int knapsack(int value[], int weight[], int n, int C,
         vector < int >&back)
{
    int *M = new int[C + 1];
    int k;
    int i, j, tmp, pos;
    for (i = 1; i <= C; i++) {
        M[i] = M[i - 1];
        pos = i - 1;
        for (j = 0; j < n; j++) {
            k = i - …

我正在使用动态编程解决Haskell中的背包问题.我的第一次尝试是建立一个二维表.但是当输入很大时(例如100*3190802表),内存容易被炸毁.

知道任何给定的行i只依赖于行(i - 1),我改为编写一个函数,希望利用尾递归:

import Data.Vector (Vector, (!))
import qualified Data.Vector as V

-- n items, k capacity, vs values, ws weights
ans:: Int -> Int -> Vector Int -> Vector Int -> Int
ans n k vs ws =
    let row = initRow k vs ws
    in  row ! k

initRow :: Int -> Vector Int -> Vector Int -> Vector Int
initRow k vs ws = itbl 1 $ V.replicate (k + 1) 0 …

在给定一定的预算和组合的最大限制的情况下，我希望最大限度地增加星星的数量。

示例问题：

预算为 500 欧元，只访问允许的最大餐厅或更少，用餐并收集尽可能多的星星。

我正在寻找一种高效的算法，它可能会处理 100 万个餐厅实例，最多 10 个餐厅。

请注意，这是我昨天问的一个问题的交叉帖子： Java：基于字段获取大型对象列表的最有效组合

下面的解决方案将为r8餐厅分配每颗星 15 美元，这意味着在生成列表时，它首先将其放入列表中，剩下的 70 美元只能再获得 2 颗星，总共 4 颗星。但是，如果它足够聪明，可以跳过r8餐厅（即使它是每星级的最佳美元比率），该r1餐厅实际上是预算的更好选择，因为它的成本为 100 美元和 5 颗星。

任何人都可以帮助尝试解决问题并击败当前的解决方案吗？

import itertools

class Restaurant():
  def __init__(self, cost, stars):
    self.cost = cost
    self.stars = stars
    self.ratio = cost / stars

  def display(self):
    print("Cost: $" + str(self.cost))
    print("Stars: " + str(self.stars))
    print()

r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = …

这是一个有趣的项目,我已经开始尝试并最大化我赢得办公室曲棍球池的机会.我正在努力寻找最佳方式来选出20名球员,这些球员将在最高工资帽中给予我最高分.

例如,假设原始数据是由

1. 玩家姓名
2. 位置(前锋,前卫,守门员)
3. 预测本赛季的得分量
4. 薪水.

现在我希望20名球员能够在X工资帽中获得最高分.后来,作为第2阶段,我想做同样的事情但是在这种情况下,我只想要12名前锋,6名防守队员和2名守门员.

现在显而易见的方法是简单地进行所有可能的组合,但是虽然这将起作用,但对于500名玩家来说这不是一个有效的选择,这将有太多可能的组合.我可以添加一些智能过滤器,将500名玩家减少到前50名前锋,前30名防守队员和前15名守门员,但这仍然是一个非常缓慢的过程.

我想知道是否有其他算法来实现这一点.这只是为了娱乐而不是重要的业务请求.但如果您对如何继续有一些想法,请告诉我.

我的第一次尝试是在其他来源的帮助下使用背包算法.它似乎只与Salary一起作为参数.我正在努力弄清楚如何添加20个球员的球队参数.它在.Net中但应该很容易转换为Java.

我正在考虑做一个单独的循环来找出最好的球队,有20名球员,不管工资,然后比较两个名单,直到我找到两个名单中最高的球队.不确定.

namespace HockeyPoolCalculator
{
public class ZeroOneKnapsack
{

protected List<Item> itemList = new List<Item>();
protected int maxSalary = 0;
protected int teamSize = 0;
protected int teamSalary = 0;
protected int points = 0;
protected bool calculated = false;

public ZeroOneKnapsack() { }

public ZeroOneKnapsack(int _maxSalary)
{
setMaxSalary(_maxSalary);
}

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

public ZeroOneKnapsack(List<Item> _itemList, int _maxSalary)
{
setItemList(_itemList);
setMaxSalary(_maxSalary);
}

// calculte the solution of 0-1 …

我观看了动态编程 - Kapsack问题(YouTube).但是,我正在解决一个稍微不同的问题,其中约束是预算,价格,是双倍,而不是整数.所以我想知道如何修改它？双是"连续"不像整数,我可以有1,2,3 ....我不认为我做0.0,0.1,0.2 ......？

更新1

我想通过乘以100将double转换为int.Money只有2位小数.但这意味着价值范围会非常大？

更新2

我需要解决的问题是:

物品具有价格(双倍)和满意度(整数)值.我有预算作为约束,我需要最大化满意度.

在youtube视频中,作者创建了两个2d数组,如int [numItems] [possibleCapacity(weight)].在这里,我不能预算是一个双重不整数