标签: knapsack-problem

当有超过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 …

我对背包问题有一个变体，我正在努力寻找有效的解决方案。

假设您有多组项目。每个组可以有任意数量的物品，每个物品都有一个值和重量。问题是找到总价值最大、重量小于某个限制的一组项目，并且（棘手的部分）只有包含每个组中的一个项目的集合才是有效的。

也就是说，想象一下你有数百种物品可供选择，但你必须带一份三明治、一份饮料、一份零食、一只手电筒等。不仅你不能从任何一组中拿走多于一件，而且你必须至少拿走一件。如果有 g 个组，那么一天结束时总共会得到 g 个项目。

看起来这应该比基本问题更快，因为很多组合都是无效的，但我正在努力寻找解决方案。

0/1 背包动态规划算法的空间优化是使用大小等于背包容量的一维数组（例如 A），并在每次迭代 i 时简单地覆盖 A[w]（如果需要），其中A[w] 表示考虑前 i 件物品且背包容量为 w 时的总值。如果使用这种优化，是否可以通过在 DP 算法的每次迭代中保存一些额外信息来重建所选择的项目列表？例如，在 Bellman Ford 算法中可以实现类似的空间优化，只要我们保留前驱指针列表，即最后一跳（或第一跳，取决于源/正在编写面向目的地的算法）。

作为参考，这是我使用动态规划解决 0/1 背包问题的 C++ 函数，其中我构造了一个二维向量 ans，使得 ans[i][j] 表示考虑前 i 个项目和背包容量 j 的总值。我重建通过反向遍历这个向量 ans 选择的项目：

void knapsack(vector<int> v,vector<int>w,int cap){
 //v[i]=value of item i-1
 //w[i]=weight of item i-1, cap=knapsack capacity
 //ans[i][j]=total value if considering 1st i items and capacity j
 vector <vector<int> > ans(v.size()+1,vector<int>(cap+1));

 //value with 0 items is 0
 ans[0]=vector<int>(cap+1,0);

 //value with 0 capacity is 0
 for (uint i=1;i<v.size()+1;i++){
    ans[i][0]=0;
 }

 //dp
 for (uint i=1;i<v.size()+1;i++) …

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

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

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

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 …

我正在努力寻找计算运输所需箱子尺寸的最佳方法.

我有3个不同尺寸的集装箱.我在数据库中定义了产品的宽度,长度,深度和质量.

我想知道如何找到最小数量的箱子,以及购物车中物品数量的最小尺寸.

我当前的'想法'是找到整个产品阵列的最大宽度,根据它选择一个框,然后根据需要拆分订单...这似乎不起作用.

我的盒子尺寸为: - 8 x 6 x 6 = 228立方英寸 - 10 x 8 x 8 = 640立方英寸 - 12.5 x 12.5 x 12.5 = 1953.125立方英寸

产品定义如下:

 [Product] => Array
                (
                    [STOCK_CODE] => 010003
                    [Product_Slug] => GABA_010003
                    [ItemName] => GABA
                    [WHOLESALE_PRICE] => 17.47
                    [RETAIL_PRICE] => 24.95
                    [Brand] => 
                    [ProductLine] => 
                    [image_name] => 705077000440
                    [MASS] => 0.313
                    [Height] => 4.625
                    [Width] => 2.375
                    [Depth] => 2.375
                    [cubic_inches] => 26.087890625
                )

我已经研究过背包问题,包装问题等,但找不到办法.任何帮助都会很棒.

function shipping(){

        $this->CartProduct->unbindModel(
            array('belongsTo' => array('User'))
        ); …

我有一个问题,我的回溯功能它循环与某些数据我不能写在这里整个程序代码,但可以把我的功能.

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{

    if(moneyA == half)
        return true;
    else if(index >= quantity)
        return false;

    moneyA += values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = true;
        return true;
    };

    moneyA -= values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = false;
        return true;
    };

    return false;
}

现在这里是解释:

quantity - values中的元素数量数组
值 - 数字数组
index - 用于控制递归的
变量moneyA - 存储元素之和的变量,数组值的
一半 - moneyA在递归完成后应该达到的数字
ifChosen - 布尔元素的数组指数组值

该函数获取值为数组的元素数量,值为一个数组,其中数字从最高到最低排序,索引控制递归,默认为0,因此它从第一个元素moneyA变量开始,该变量存储来自values数组,它应该达到一半,这是从数值数组中取出的数字的一半,ifChosen存储了所选择的数字.

整个函数执行此操作,它将值数组中的元素相加并检查它是否达到了一半,如果它低于一半将其添加到moneyA并标记为ifChosen然后它转到下一个,如果总和高于一半它回来并在ifChosen数组中取消标记并从moneyA中减去.应始终获得最高要素. …

我很好奇是否有可能修改（或使用）无限制背包问题的DP算法，以使背包中物品的总价值最小化，同时使总重量至少达到一些最小约束C。

自底向上的DP算法，用于UKP的最大化版本：

let w = set of weights (0-indexed)

and v = set of values (0-indexed)

    DP[i][j] = max{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] }

for i = 0,...,N and j = 0,...,C

given DP[0][j] = 0 and DP[i][0] = 0

where N = amount of items

and C = maximum weight

DP[N][C] = the maximum value of items for a knapsack capacity of C 

我们可以使UKP最小化吗？如果没有，谁能提供其他解决方案或技术来解决这样的问题？

谢谢，丹

问题如下:

您有n个行程长度(以km为单位),应在m天之间进行划分,以使每天最大长度总和最小化.例如,在3天内划分的行程长度[1,5,2,6,8,3,2]导致[1,5,2] [6] [8,3,2]因为最大日长度总和是我们能达到的最低点.

是否有一种描述处理这种问题的算法？我遇到了bin包装和背包问题,但没有一个能解决我的问题.我可以想象它可能是对bin包装的一点修改但是没有得出结论.

*不是家庭作业*

我已经在python中实现了背包并且我成功地获得了最好的价值但是我想扩展问题以填充所有权重和项目的背包表的所有适当值的表.

我已经在python中实现了它,我是新手,所以请告诉我,如果有什么我可以改进,但概念应该适用于任何语言.

values, weights, table = [], [], [[]]

def knapsack(i, W):
    global weights, values, table, counter
    if (i < 0):
        # Base case
        return 0
    if (weights[i] > W):
        # Recursion
        return knapsack(i - 1, W)
    else:
        # Recursion
        return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))

def main():
    global values, weights, table
    W = int(input())
    values = list(map(int, input().split()))
    weights = list(map(int, input().split()))
    # initalise table with 0's
    table = [[0 for …