时间戳

首页 > 解决方案 > 动态规划：最小浪费和最小批量

php - 动态规划：最小浪费和最小批量

问题描述

我正在做一个项目，我需要以这样的优化格式创建数据，它不会使框架减慢太多。
问题是：假设您从我的电子商务商店
订购了12 件产品。对于该产品，我有5 种不同的捆绑包可以提供这么多数量。
假设捆绑包的数组以序列号为键，该捆绑包中可用的最大单位为值，如下所示： 

$arr = array(
array('sr_no1'=>5),
array('sr_no2'=>7),
array('sr_no3'=>2),
array('sr_no4'=>9),
array('sr_no5'=>12)
);

现在，我的贪婪方法有两个主要条件来放弃客户要求的数量。

  1. 应该有最小的浪费，例如如果您订购 11 个单位，那么您将给出 9+2-11=0 浪费，而不是从 12-11=1 浪费
  2. 值应从最小批次/捆绑数量中选择，例如如果您订购 12 个单位，则有 5+7-12=0 浪费和 12-12=0 浪费，因此我们将选择 array('sr_no5'=>12)赠送所要求的数量。

我一直在试图找出过去 3 天的解决方案。

考虑订购数量为 12 或 11 或 6 或 35 或 30 等的测试用例。

因此，我需要的是我们将选择分配数量的数组，例如 array('sr_no5'=>12) 用于赠送 12 个订购数量单位和数组 array('sr_no3'=>2),array( 'sr_no4'=>9) 用于赠送 11 个单位的数量。

在试图找出解决方案时，我尝试了背包、贪婪和最小生成树。
请找到最优化的解决方案，因为我们不想实现服务器超时。

注意：上面的所有值，如订购的数量/单位，没有。捆绑包中，每个捆绑包中的最大可用单位是变量，可以更改为任何数量。的案例。

标签： phpdynamic-programmingknapsack-problemgreedyminimum-spanning-tree

解决方案

不确定算法，但您可以通过为每个捆绑包分配 0 或 1 的二进制文件来查看所有可能的结果。11000 将等于 5+7+0+0+0 (12)，00010 将等于 0+0+0+9 +0 等

然后根据该伪二进制值和给出的总数构建一个主数组。

然后按匹配（或最接近的匹配）过滤，看看哪个结果的 1 最少。它很粗糙，但会起作用。

推荐阅读