标签: knapsack-problem

在最近由“AmDocs”组织的比赛中，我遇到了以下问题：（问题的基本思想）

你是一个固定大小的矩阵 12x12。您将获得六个长度为 6、5、5、4、3、2 的线段。矩阵有空的空间和填充的空间。您必须返回 "Yes" 或 "No" ，无论所有 6 条线段是否可以同时适合矩阵。线条只能水平或垂直放置。

应该使用什么算法来解决这个问题？包装 ？背包？

我正在阅读Knapsack Problem(无界),正如我理解DP中的经典之作.
虽然我认为我在阅读时理解了解决方案,但我不清楚如何将其转换为实际代码.
例如,在以下重复"公式"中:

M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1

我不知道如何将其转换为代码,因为我不清楚内部MAX应该在那里还是应该只是代替:
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1

有什么帮助找出公式并编码吗？

我正在尝试解决背包问题,这也是整数编程问题.我已经研究了几种近似解决方案,如动态编程,贪婪算法,分支定界算法,遗传算法.你能告诉我一个库(用任何语言)来帮助实现任何/所有这些算法吗？

提前致谢.

题：

一次考试由 N 道题组成。N题的分数分别为m1、m2、m3、..mN。Jam 正在参加考试，他想最大限度地提高自己的分数。然而，他需要一些时间来解决每一个问题。他解题所用的时间分别为t1、t2、t3、..tN。考试总共持续时间 T。但是 Jam 的老师非常聪明，她知道 Jam 会找到获得最高分的方法。所以，为了迷惑 Jam，她还为他提供了一个奖励——这个提议是 Jam 可以选择一个问题，他可以将该问题的分数加倍。现在，Jam 确实很困惑。帮助他找出他可以获得的最大分数。

约束

1<=N<=1000

1<=T<=10000

1<=mi<=100000

1<=ti<=10000

我在这里尝试了这个问题，并提出了以下算法：

既然问题说，我们可以选择一个问题，他可以为该问题的分数加倍。

所以，为了选择那个问题，我应用了贪婪的方法，即。

1. 应该选择具有较大（分数/时间）比率的问题，他可以为该问题获得两倍的分数。

2. 如果该比率也相同，则应选择分数较大的问题。

   就我理解的问题而言，剩下的就是简单的背包。我尝试了以下实现，但得到了错误的答案。对于给定的测试用例，我的代码给出了正确的输出

   3 10 1 2 3 4 3 4

我已经尝试了评论部分给出的这个测试用例，我的代码给出了 16 作为输出，但答案应该是 18

  3 
  9
  9 6 5
  8 5 3

蛮力方法会超过时间限制，因为解决 N 个背包的复杂度为 O(nW) 将给出 O(n^2 W) 的整体时间复杂度我认为可以为这个问题开发一个更具体的算法。有没有人有比这更好的主意？

谢谢

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int T[2][10002];
    int a[1000002],b[100002];
    float c[100002];
    int knapSack(int W,int val[],int wgt[],int n)
    {
    int i,j;

    for(i=0;i<n+1;i++)
    { …

我有一个与0-1背包类似的问题。

我试图做的修改是获取所选对象的列表，而不是成本。我尝试使用以下代码：

public static int fillPackage(double weight,ArrayList<Item> item, int n) {
    //base case
    if(n == 0 || weight == 0)
        return 0;

    if(item.get(n - 1).getWeight() > weight)
        return fillPackage(weight, item, n - 1);    

    else {
        int include_cost = item.get(n - 1).getCost() + fillPackage((weight - item.get(n - 1).getWeight()), item, n - 1);
        int exclude_cost = fillPackage(weight, item, n - 1);
        if(include_cost > exclude_cost) {
            my_pack.add(item.get(n - 1));
            return include_cost;
        }
        else {
            return exclude_cost;
        }
    }   
}

这my_pack …

这个来自adagio函数knapsack()的CRAN文档的摘录按预期运行 - 它解决了利润向量p,权重向量w和容量的背包问题cap,选择具有最大利润的元素子集受限于总权重选定的元素不超过容量.

library(adagio)
p <- c(15, 100, 90, 60, 40, 15, 10,  1)
w <- c( 2,  20, 20, 30, 40, 30, 60, 10)
cap <- 102
(is <- knapsack(w, p, cap))

如何向解决方案添加矢量长度约束并仍然获得最佳答案？例如,上面的练习,但选定的子集必须包含正好三个元素.

我正在尝试用给定条件编写背包c#算法,但我遇到的问题总是存在两个问题.我得到"索引超出了数组的范围"错误或我的结果只是0.

我找到了几个Knapsack实现的代码示例,但是我无法弄清楚我做错了什么.

代码示例:https: //www.programmingalgorithms.com/algorithm/knapsack-problem

http://www.csharpstar.com/csharp-knapsack-problem/

我的代码:

static int Knapsack(int n, int w, int[] s, int[] v)
{
    int[,] G = new int[n+1,w+1];
    for (int k = 0; k <= n; k++)
    {
        for (int r = 0; r < w; r++)
        {
            if (r == 0 || k == 0)
                G[k, r] = 0;
            else if (s[k] <= r)
                G[k, r] = Math.Max(G[k- 1, r], v[k] + G[k - 1, r - s[k]]);
            else
                G[k, r] = G[k …

解决与背包问题相关的问题的最佳方法是什么？背包问题有 3 个变量，例如：价值、重量和体积？（最大可能的值，最大重量和体积限制）

我曾尝试使用定义的索引，基于其值/（权重*体积），但我相信这不会给我最好的解决方案，所以我进行了搜索，有些人建议使用动态编程，但所有与此相关的主题，只有 2 个变量（值和权重），我不知道超过 2 个变量会如何影响这一点。

该代码是针对 0/1 背包问题的递归动态规划。所以让我首先说代码似乎是正确的，因为当我运行它时，它会显示结果，但前提是我取消注释该printf行（请参阅突出显示的部分）并且它与解决方案无关（我仅将其用于测试目的），我觉得这很奇怪。有人可以告诉我为什么会这样。

int main() {    

    int DP_Recursive(int W, static int wt[], static int val[], int n, static int dp[][]);

    static int wt[5] = { 5, 10, 20, 30 };
    static int val[5] = { 50, 60, 100, 120 };

    static int dp[5][60]; //marker 2-D array

    for (int i = 0; i <= 5; i++) {
        for (int w = 0; w <= 50; w++) {
            dp[i][w] = -1;
        }
    }

    printf("The total loot is %d$.", DP_Recursive(50, wt, …

我是 Haskell 的新手，并且一直在通过做一些简单的编程挑战来练习。最近两天，我一直在尝试在这里实现无界背包问题。维基百科页面上描述了我使用的算法，但对于这个问题，“重量”一词被替换为“长度”一词。无论如何，我开始编写没有记忆的代码：

maxValue :: [(Int,Int)] -> Int -> Int
maxValue [] len = 0
maxValue ((l, val): other) len =
    if l > len then 
        skipValue
    else 
        max skipValue takeValue
    where skipValue = maxValue other len
          takeValue = (val + maxValue ([(l, val)] ++ other) (len - l)

我曾希望 haskell 会很好，并且有一些很好的语法#pragma memoize来帮助我，但是四处寻找示例，解决方案是用这个斐波那契问题代码解释的。

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = …