algorithm - 是否可以限制线性分区问题中的部分大小?
问题描述
我有一个工程问题,需要我将一组正数划分为 k 个部分,而不改变集合中数字的顺序,以便各部分的总和尽可能相等。我知道这个“线性分区问题”有一些解决方案。事实上,我已经成功地尝试了动态编程解决方案并且它有效。
现在的问题是:如果零件有最大尺寸限制怎么办?(“任何部分都不能超过 m 项”)它可以添加到例如 DP 解决方案中,还是可以使用其他一些技术来解决这个问题。
感谢所有评论、链接和建议。
编辑:我在下面添加了原始算法的粗略草图
// Partition number array seq to k parts with max number of m items in each part
public void LinearPartition(double[] seq, int k, int m)
{
double[,] table;
int[,] solution;
int n = seq.Length - 1;
linearPartitionTable(seq, k, m, out table, out solution);
k = k - 2;
while (k >= 0)
{
Console.WriteLine(solution[n - 1, k] + 1);
n = solution[n - 1, k];
k--;
}
}
private void linearPartitionTable(double[] seq, int k, int m,
out double[,] table, out int[,] solution)
{
int n = seq.Length;
table = new double[n, k];
solution = new int[n - 1, k - 1];
table[0, 0] = 0;
for (int i = 1; i < n; i++)
table[i, 0] = seq[i] + table[i - 1, 0];
for (int j = 0; j < k; j++)
table[0, j] = seq[0];
for (int i = 1; i < n; i++)
{
for (int j = 1; j < k; j++)
{
double currentMin = double.MaxValue;
int minX = 0;
for (int x = 0; x < i; x++)
{
double cost = Math.Max(table[x, j - 1], table[i, 0] - table[x, 0]);
if (cost < currentMin)
{
currentMin = cost;
minX = x;
}
}
table[i, j] = currentMin;
solution[i - 1, j - 1] = minX;
}
}
}
解决方案
推荐阅读
- python - 使用 pandas.DataFrame.assign 时将多个变量传递给函数
- ios - 有什么方法可以在 iOS swift 中支持用于支付卡的 NFC 读取器?
- javascript - 如何获取由 XLSX 模块提取的 excel 文件生成的数组元素而不会未定义
- javascript - 使用自定义浏览器协议启动 nodejs 应用程序
- powershell - 在 powershell core 7.1.3 中安装 pscx 失败
- java - 任务 ':app:installDebug' 执行失败。> com.android.builder.testing.api.DeviceException:com.android.ddmlib.InstallException:EOF
- angular - 运行我的文件更改事件侦听器导致 TypeError:无法在“FileReader”上执行“readAsArrayBuffer”:参数 1 不是“Blob”类型
- git - Git 中的 TAG 名称标准
- git - 发布生成 git 日志输出后,如何从 X、Y、Z 板上找到所有故事编号?并将列表存储在变量中?
- java - 为什么我的 HashMap 内的值循环停止?