标签: knapsack-problem

假设我有一个代表篮球运动员及其姓名、位置、成本和预计得分的元组列表，

listOfPlayers = [
                 ("Player1","PG",Cost,projectedPoints),
                 ("Player2","PG",Cost,projectedPoints),
                 ("Player3","SG",Cost,projectedPoints),
                 ("Player4","SG",Cost,projectedPoints),
                 ("Player5","SF",Cost,projectedPoints),
                 ("Player6","SF",Cost,projectedPoints),
                 ("Player7","PF",Cost,projectedPoints),
                 ("Player8","PF",Cost,projectedPoints),
                 ("Player9","C",Cost,projectedPoints),
                 ("Player10","C",Cost,projectedPoints) 
                ]

假设所有名称、成本和预测点都是可变的。

我正在处理一个传统的背包问题，他们可以根据给定的重量对背包进行分类和包装。但这并没有考虑到头寸。
我想知道是否有一种方法可以编辑背包代码以仅包含每个位置之一，即（pg，sg，sf，pf，c）。

传统的 0/1 背包可以做到这一点还是我需要切换到其他东西？

我已经挣扎了近一周的任务而没有成功找到解决方案,所以这个网站是我最后的希望.

我有0-1背包问题,有20个项目具有不同的值和重量,最大重量为524.现在我需要实施蛮力找到20个项目的最佳解决方案子集,使总权重<= 524和最大值选择的项目.

能否请您指出或更好地详细实施以分析它是如何工作的!非常感谢你

在维基百科中，背包的算法如下：

for i from 1 to n do  
  for j from 0 to W do  
    if j >= w[i] then  
      T[i, j] := max(T[i-1, j], T[i-1, j-w[i]] + v[i]) [18]  
    else  
      T[i, j] := T[i-1, j]  
    end if  
  end for  
end for  

它与我在网上找到的所有示例的结构相同。
我无法理解的是，这段代码如何考虑到最大值可能来自较小的背包这一事实？例如，如果背包容量为 8，那么最大值可能来自容量 7 (8 - 1)。
我找不到任何逻辑来考虑最大值可能来自较小的背包。这是错误的想法吗？

如何找到不超过某个值的最大项目总和？例如，我有45个这样的值：1.0986122886681098、1.6094379124341003、3.970291913552122、3.1354942159291497、2.5649493574615367。我需要找到不超过 30.7623 的最大可能组合。

我无法使用暴力来找到所有组合，因为组合的数量将会很大。所以我需要使用一些贪心算法。

这是硬币兑换问题的一个版本。因此，这是一个动态规划问题。

我知道如何确定您是否可以找零，如果您最多可以使用每种面额的一枚硬币，或者您最多可以使用 k 枚硬币，但不能同时使用两者。

我有一个动态的编程问题,我花了几个小时研究无济于事.

第一部分很简单:你有一个背包物品,你必须最大化这些物品的价值,同时保持低于一定的重量.

问题的第二部分是相同的,除了现在还有一个项目限制.例如:

您可以放入包中的物品的最大价值是什么,以便在重量和物品限制的情况下最大化价值？

我不知道如何实现这个问题的第二部分,我正在寻找一般的算法.

我有一个背包问题的简单解决方案的代码，我想获取所选项目的索引列表，目前它正在返回所选项目的值的总和。任何帮助将不胜感激。Java代码：

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{

    // A utility function that returns maximum of two integers

     static int max(int a, int b) {

        return (a > b)? a : b; }

     // Returns the maximum value that can be put in …

我有一个包含两列的数据框

df = DataFrame.from_records([
  {"time": 10, "amount": 200},
  {"time": 70, "amount": 1000},
  {"time": 10, "amount": 300},
  {"time": 10, "amount": 100},
])

我想要，给定一段时间80ms，计算可能的最大数量，在这种情况下，输出应该是 1300，因为在此期间，可能的最大数量是 1300。

熊猫可以吗？我想过使用聚合，但我不知道如何使用它

我有一组N数字,每个数字附加一些费用,问题是选择所有可能的数字组作为列表,使其产品小于一定数量M,根据成本总和进行排序.

例如: - 这组数字是

(number, costOfThatNumber) : {(90, 10) , (80, 20), (60, 40), (40, 60), (15, 85)},

并且产品必须小于Prod <= 1000,

可能的解决方案是: -

[Solution 1 :- {(15, 85), (40, 60)} :- Product = 600 (which is less than, 1000), cost = 85 + 60 = 145]
[Solution 2 :- {(15, 85), (80, 20)} :- Product = 900 and cost = 105]

所以列表变成,{Solution2, Solution1}.

PS: -

1. 这不是一个家庭作业问题,在接受采访时被问到.我只被问到算法,我只能说它看起来有点像背包问题,但是用于乘法.
2. 如果我无法正确解释问题,请原谅.

我正在尝试用输入解决分数背包问题,

[("label 1", value, weight), ("label 2", value, weight), ...]

和输出,

[("label 1", value, solution_weight), ("label 2", value, solution_weight), ...]

但我一直收到错误computeKnapsack:

"Couldn't match expected type `(t1, t2, t0)' with actual type `[a0]`"

我无法理解问题可能是什么.我正在尝试创建一个三项目元组列表.我怎样才能让它停止期待一个3入口的元组？

fst3 (a,b,c) = a
snd3 (a,b,c) = b
trd3 (a,b,c) = c
fst4 (a,b,c,d) = a
snd4 (a,b,c,d) = b
trd4 (a,b,c,d) = c
qud4 (a,b,c,d) = d

sortFrac (a1, b1, c1, d1) (a2, b2, c2, d2)
  | d1 > d2 = GT
  | d1 …

好的,所以我正在尝试解决背包问题.

在小输入情况下,程序运行没有问题并提供最佳解决方案,但是当输入大小很大,或者输入文件中的数字变大时,程序会给我一个分段错误.我不明白为什么会发生这种情况,因为INT的最大值也超过了这些数字中的任何一个.

这是我的代码.

    #include<stdio.h>
    #include<stdlib.h>
    int main(void)
    {
        int W,n,i,j,k ;
        scanf("%d %d",&W,&n); // capacity of knapsack and number of total items
        int value[n+1],weight[n+1];
        int** A;
        A = (int **)malloc((n+1)*sizeof(int*));
        for(i=0;i<W+1;i++)
            A[i]=(int *)malloc(sizeof(int)*(W+1));
        for(i=1;i<n+1;i++)
        {
            scanf("%d %d",&value[i],&weight[i]); //taking value and weight of each item
        }
        for(i=0;i<W+1;i++)
            A[0][i]=0;
        for(i=0;i<n+1;i++)
            A[i][0]=0;
        for(i=1;i<n+1;i++)
        {   
            for(j=1;j<W+1;j++)
            {
                if(j-weight[i]<0)
                {
                    A[1][j]=A[0][j];
                }
                else
                {
                    if(A[0][j]>A[0][j-weight[i]]+value[i])
                        A[1][j]=A[0][j];
                    else
                        A[1][j]=A[0][j-weight[i]]+value[i];
                }
            }
            for(k=0;k<W+1;k++)
                A[0][k]=A[1][k];
        }   
        int max=0;
        i=1;
        for(i=0;i<2;i++)
            for(j=0;j<W+1;j++)
            {
                if(A[i][j]>max)
                    max=A[i][j];
            }
        printf("%d\n",max);
        return(0);
    } …

我正在寻找一个案例,其中贪婪算法选择具有重量<最大重量并且首先放入背包的最高值/重量比的物品将不起作用.有没有人有例子？因为否则,贪婪的最坏情况将是O(nlogn)(nlogn以降序值/权重排序,n来经历它),而动态编程方式的最坏情况是O(nW),使logn <时贪婪更快W.