这是一个硬算法问题:

将列表分成两部分(总和),它们的总和最接近(大多数)彼此

列表长度为1 <= n <= 100且问题中给出的(数字)权重1 <= w <= 250.

例如:23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

我有一个算法,但它并不适用于所有输入.

1. 在里面.列表list1 = [],list2 = []
2. 排序元素(给定列表)[23 32 34 65 95 123 134]
3. 弹出最后一个(最多一个)
4. 插入到不同的列表中

实现:list1 = [],list2 = []

1. 选择134插入列表1.list1 = [134]
2. 选择123插入列表2.因为如果你插入list1差异越来越大
   3.选择95并插入list2.因为sum(list2)+ 95 - sum(list1)较少.

等等...

这是一个有趣的项目,我已经开始尝试并最大化我赢得办公室曲棍球池的机会.我正在努力寻找最佳方式来选出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 …

我有一个问题,表面看起来像0-1背包.我有一组可以选择(或不选择)的可能"候选人",每个候选人都有"权重"(成本)和潜在的"价值".如果这是整个问题,我会使用DP方法并完成它.但是这里是曲线球:对最终解决方案中可能的候选者存在"分区约束".

我的意思是候选空间被分成不连续的等价类.对于我的特殊问题,大约有300个候选人和12个可能的等同类.有"商务规则"说我只能说C1级的3名候选人和C2级的6名候选人.

这种约束建议使用分支定界技术或其他形式的修剪的图搜索类型方法,但是由于我只熟悉0-1背包的DP解决方案,我有点难以理解.哪些技术/方法可能适合这个问题？我也想过可能使用约束编程库但不确定它是否能够找到解决方案？

我正在尝试使用分支和边界来解决这个背包问题的C++实现.这个网站上有一个Java版本:实现分支和绑定背包

我正在努力让我的C++版本打印出它应该的90,但它没有这样做,相反,它打印出5.

有谁知道问题出在哪里？

#include <queue>
#include <iostream>
using namespace std;

struct node
{
    int level;
    int profit;
    int weight;
    int bound;
};

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)
{
    int j = 0, k = 0;
    int totweight = 0;
    int result = 0;

    if (u.weight >= W)
    {
        return 0;
    }
    else
    {
        result = u.profit;
        j = u.level + 1;
        totweight = u.weight;

        while ((j < n) && (totweight + wVa[j] <= …

在我发现的每个示例中，使用动态编程针对1/0背包问题进行了动态编程，其中项目具有权重（成本）和利润，它从未明确表示要对项目列表进行排序，但是在所有示例中，它们都通过增加两个值来进行排序权重和利润（示例中权重越高，利润越高）。所以我的问题是，当从项目数组/列表中将项目添加到矩阵中时，我可以按任何顺序添加它们，还是添加权重或利润最小的项目？因为从多个示例中我发现我不确定这是否只是一个巧合，否则您实际上每次确实需要将最小的权重/利润放入矩阵中

假设你有一个圆圈(如下图所示),有N个斑点,你有N个珠子分布在插槽中.

这是一个例子:

每个珠子可以顺时针移动X个槽,成本为X ^ 2美元.你的目标是在每个插槽中最终得到一个珠子.为实现这项任务,您需要花费的最低金额是多少？

这个问题更有趣的变化:分配珠子拼图的算法(2)？

任务关键型生产系统有n个阶段,必须按顺序执行; 阶段i由机器M_i执行.

每个机器M_i具有可靠地运行的概率r_i和失败的概率1-r_i(并且故障是独立的).因此,如果我们用一台机器实现每个阶段,整个系统工作的概率是r_1,r_2,...,r_n.为了提高这种可能性,我们通过使用执行阶段i的机器M_i的m_i个副本来添加冗余.

所有m_i拷贝同时失败的概率仅为(1-r_i)^(m_i),因此阶段i正确完成的概率为1-(1-r_i)^(mi),整个系统工作的概率为PROD(I = 1,N){1-(1-R_I)^(M_I)}.

每台机器M_i的成本为c_i,购买机器的总预算为B. (假设B和c_i是正整数.)在给出概率r_1,...,r_n,成本c_1,...,c_n和预算B的java代码中写入算法,找到冗余m_1,... .,m_n在可用预算范围内,并最大化系统正常工作的概率(确定可实现的最大可靠性).此外,还要显示每种类型的机器在预算范围内达到可靠性的程度.

所以我读了一个文件,它给了我允许的总预算,然后是机器的数量,然后我读到的每台机器的成本和可靠性.我将成本和可靠性存储在两个链表中(不确定这是否最好).

  try {
            BufferedReader newFileBuffer = new BufferedReader(new     FileReader(inputFile));
            budget = Integer.parseInt(newFileBuffer.readLine()); 
            numberOfMachines = Integer.parseInt(newFileBuffer.readLine()); 
            while ((fileLine  = newFileBuffer.readLine()) != null) 
            {       
                line = fileLine.split(" ");

                try 
                {
                    cost.add(Integer.parseInt(line[0]));
                    totalCostOfOneEach += Integer.parseInt(line[0]); 
                    reliability.add(Float.parseFloat(line[1]));
                } catch (NumberFormatException nfe) {};

            }
            newFileBuffer.close();
        } catch (Exception e) 
        {
            e.printStackTrace();
        }

从那里我知道每台机器中的一台必须使用一次,所以我按每台机器之一(totalCostOfOneEach)的总成本减去预算,如果你愿意,这会让我超出预算或冗余预算.

bRedundent = (budget - totalCostOfOneEach);

现在是我被卡住的地方,我迷失了什么循环找到解决方案.我已经研究并找到了这个解决方案,但我不明白这条线

Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k}

所以我所知道的是我创建了一个双数组并且我将数组初始化为:

double[][] finalRel = new double[numberOfMachines][bRedundent]; 
for (int j = 0; j < …

我目前正在实现一个动态编程算法来解决背包问题.因此我的代码有两个for循环,一个外循环和一个内循环.

从逻辑的角度来看,我可以并行化内部for循环,因为它们之间的计算是相互独立的.由于依赖性,外部for循环不能并行化.

所以这是我的第一个方法:

for(int i=1; i < itemRows; i++){
        int itemsIndex = i-1;
        int itemWeight = integerItems[itemsIndex].weight;
        int itemWorth = integerItems[itemsIndex].worth;

        #pragma omp parallel for if(weightColumns > THRESHOLD)
        for(int c=1; c < weightColumns; c++){
            if(c < itemWeight){
                table[i][c] = table[i-1][c];
            }else{
                int worthOfNotUsingItem = table[i-1][c];
                int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                table[i][c] = worthOfNotUsingItem < worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
            }
        }
}

代码运行良好,算法正确解决了问题.然后我考虑优化这个,因为我不确定OpenMP的线程管理是如何工作的.我想在每次迭代期间防止不必要的线程初始化,因此我在外部循环周围放置了一个外部并行块.

第二种方法:

#pragma omp parallel if(weightColumns > THRESHOLD)
{
    for(int i=1; i < itemRows; i++){ …

我一直在寻找多项选择背包问题的python实现。到目前为止，我在 github 中找到了一个 java 实现：https : //github.com/tmarinkovic/multiple-choice-knapsack-problem

还有一个psedu代码：http : //www.or.deis.unibo.it/kp/Chapter6.pdf

我还没有找到一个 python 实现。如果有图书馆实施多项选择背包问题，我将不胜感激。

我已经获得了证明,会抹黑关于0/1背包问题的一个普遍持有的想法,我真的有一个很难说服我自己我是对的,因为我无法找到任何东西任何地方支持我的要求,所以我将首先陈述我的主张,然后证明他们,我将感谢任何人试图进一步证实我的主张或取消他们.任何合作都表示赞赏.

断言:

1. 用于解决背包问题的bnb(分支和边界)算法的大小不与K(背包的容量)无关.
2. bnb树完整空间的大小始终为O(NK),N为项目数而不是 O(2 ^ N)
3. bnb算法总是比时间和空间上的标准动态编程方法更好.

预先假设:bnb算法倾向于无效节点(如果剩余容量小于当前项的权重,我们不会扩展它.此外,bnb算法以深度优先的方式完成.

邋proof证明:

这是解决背包问题的递归公式:

值(i,k)= max(值(i-1,k),值(n-1,k-weight(i))+值(i)

但是如果k <weight(i):Value(i,k)= Value(i-1,k)

现在想象这个例子:

K = 9
N = 3   
V W:   
5 4   
6 5   
3 2

现在这里是针对此问题的动态解决方案和表:

现在想象一下,不管它是否是一个好主意,我们都希望通过memoization而不是表格使用递归公式,使用类似地图/字典或简单数组来存储访问过的单元格.为了使用memoization解决这个问题,我们应该解决所表示的单元格:

现在这就像我们使用bnb方法获得的树一样:

而现在的邋proof证明:

1. Memoization和bnb树具有相同数量的节点
2. 记忆节点取决于表大小
3. 表大小取决于N和K.
4. 因此 bnb不依赖于K.
5. 记忆空间受NK即O(NK)的限制
6. 因此, bnb树完整空间(或者如果我们以广度优先的方式执行bnb的空间)总是O(NK)而不是O(N ^ 2)因为整个树不会被构造而且它将是精确的喜欢妈妈.
7. Memoization比标准动态编程具有更好的空间.
8. bnb比动态编程有更好的空间(即使首先在广度上完成)
9. 没有松弛的简单bnb(只是消除不可行节点)将比memoization有更好的时间(memoization必须在查找表中搜索,即使查找可忽略不计,它们仍然是相同的.)
10. 如果我们忽略了memoization的查找搜索,那么它比动态更好.
11. 因此, bnb算法在时间和空间上总是优于动态.

问题:

如果无论如何我的证据都是正确的,那么会出现一些有趣的问题:

1. 为什么要烦扰动态编程呢？根据我的经验,你可以在dp背包中做的最好的事情就是拥有最后两列你可以将它进一步改进到一列,如果你从下到上填充它,它将有O(K)空间但仍然不能(如果上述断言是正确的)击败bnb方法.
2. 如果我们将它与松弛修剪(关于时间)相结合,我们还能说bnb更好吗？

ps:很抱歉很长的帖子!

编辑:

由于两个答案都集中在记忆化,我只是想澄清,我没有关注这个在所有!我只是用memoization作为一种技术来证明我的断言.我的主要关注点是分支定界技术与动态规划,这里是另一个问题的完整例子,由bnb + relax解决(来源:Coursera - 离散优化):