我试图用最少的水滴或浪费来筑巢材料.

Table A

Qty Type Description Length

2   W    16x19       16'
3   W    16x19       12'
5   W    16x19       5'
2   W    5x9         3'


Table B

Type Description StockLength

W    16X19       20'
W    16X19       25'
W    16X19       40'
W    5X9         20'

我一直在寻找贪心算法,Bin装箱,背包,1D-CSP,分支机构,蛮力等等.我很确定这是一个切割库存问题.我只是需要帮助来提供运行它的功能.我不只是有一个库存长度而是多个,并且用户可以输入他自己的不常见长度的库存.任何帮助计算在PHP中使用的函数或算法来提出最少的浪费所需的优化切割模式和库存长度将非常感激.

谢谢

是否可以解决以下0-1背包问题:

• '浮动'正值和
• '浮动'权重(可以是正数或负数)
• 背包的"漂浮"能力> 0

我平均有10个项目,所以我正在考虑使用暴力实施.但是,我想知道是否有更好的方法.

#include<stdio.h>

int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}

void knapsack(int m,int n,int w[],int p[])
{
    int v[10][10],x[10],i,j;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            if(j==0||i==0)
                v[i][j]=0;
            if(j-w[i]<0)
                v[i][j]=v[i-1][j];
            else
                v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
        }
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
            printf("%d\t",v[i][j]);
        printf("\n");
    }
    printf("THE OPTIMAL SOLUTION IS:%d",v[n][m]);
    for(i=1;i<=n;i++)
        x[i]=0;
    i=n;
    j=m;
    while(i>0 && j>0)
    {
        if(v[i][j]!=v[i-1][j])
        {
            x[i]=1;
            j=j-w[i];
        }
        i--;
    }
    printf("THE OPTIMAL SET OF WEIGHTS IS:");
    for(i=1;i<=n;i++)
        if(x[i]==1)
            printf("%d\t",i);
    printf("\n");
}

int main()
{
    int w[10],p[10],i,m,n;
    printf("ENTER THE NUMBER OF ITEMS:"); …

在我的代码中,假设C是容量,N是项目的数量,w [j]是项目j的权重,v [j]是项目j的值,它是否与0-做同样的事情1背包算法？我一直在尝试我的代码在一些数据集上,似乎是这种情况.我之所以想知道这是因为我们教过的0-1背包算法是二维的,而这是一维的:

for (int j = 0; j < N; j++) {
    if (C-w[j] < 0) continue;
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
        dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
    }
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);

这是我对0-1背包算法的实现:(具有相同的变量)

for (int i = 0; i < N; i++) {
    for (int j = 0; j …

我对理解动态编程有困难,所以我决定解决一些问题.我知道基本的动态算法,如最长的常见子序列,背包问题,但我知道它们因为我读过它们,但我不能自己想出一些东西:-(

例如,我们有自然数的子序列.我们可以使用加号或减号的每个数字.最后,我们取这个总和的绝对值.对于每个子序列,找到尽可能低的结果.

in1:10 3 5 4; out1:2

in2:4 11 5 5 5; out2:0

in3:10 50 60 65 90 100; out3:5

第3次解释:5 = | 10 + 50 + 60 + 65-90-100 |

更糟糕的是我的朋友告诉我这是简单的背包问题,但我在这里看不到任何背包.动态编程有些困难,还是只有我有很大问题？

我有一个优化问题.这是一个包含20个部分的产品(生产顺序无关紧要).我有3台类似的机器可以生产所有20个零件.

我用分钟表示了20个部分(即生产第一部分需要3分钟,生产第二部分需要75分钟等)

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)

因此生产1种产品需要730分钟.

sum(ItemTime)

目的是通过将好的物品分配给三台机器来最小化一种产品的生产.

sum(ItemTime/3)

所以实际上我需要尽可能接近243.333分钟(730/3)

可能性的数量巨大3 ^ 20

我想有许多不同的最佳解决方案.我希望R给我所有这些.我不需要知道需要机器1 2和3的总时间:我还需要知道给机器1,机器2和机器3提供哪些物品.

或者,如果它太长,我想选择一个尽可能合理的样本而不重复......

我可以用R语言解决我的问题吗？

我已经获得了证明,会抹黑关于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 - 离散优化):

当有超过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 个项目。

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

首先,我是一个PHP新手...所以我仍然编程和理解PHP程序.那说,

我有一个存储在数据库中的数字(数量)的集合.

问题:使用PHP和mySQL,

1. 什么是将此信息从数据库中取出的最佳方法,以使金额与其交易ID相关联

2. 最重要的是,我需要在db中找到一组匹配的数字,等于29的总和.

以下是Transaction_tlb我的数据库的事务表mydb

    Transaction_ID |     Name         |       Date      | Amount
    ---------------|------------------|-----------------|------------ 
    11012          | Jonathan May     |   6/12/2016     |     84
    21012          | John Pedesta     |   6/12/2016     |     38
    31012          | Mary Johnson     |   1/01/2017     |     12
    41012          | John Johnson     |   8/01/2017     |     13
    51012          | Keith Jayron     |   8/01/2017     |     17
    61012          | Brenda Goldson   |   8/01/2017     |     2
    71012          | Joshua Traveen   |   8/01/2017     |     78
    81012          | Remy ma …