Knaptime

这个包旨在解决背包问题的变体。

由于在线上缺乏易于访问的背包变体算法实现，因此构建了这个包。计划添加语言绑定，以便这些函数可以在您选择的任何语言中使用。

文档

查看所有变体和其他文档 这里 (链接).

测试

理想情况下，我们会有一个全面的测试套件，但这只是我的一个副项目 ;).

目前我只实现了同一种算法两次（使用递归/原始方法和优化的动态规划方法）。对这两种方法的模糊测试通常能揭示大多数实现问题。

如果您有关于如何可靠地测试 Rust 代码而不头疼的想法，我将欢迎任何证明概念的 PR :)

贡献

欢迎 PR 和错误修复！

lib.rs:

Knaptime 包

这个包旨在解决背包问题的变体。

由于在线上缺乏易于访问的背包变体算法实现，因此构建了这个包。计划添加语言绑定，以便这些函数可以在您选择的任何语言中使用。

变体

带 ! 的项目（尚未实现）。请随意打开 PR 或通过 GitHub 问题请求帮助。

[^1]: 这与常规背包不兼容，因为它是直接变体。如果您有实现无效变体的想法，请随意打开 GitHub 问题。

背包优化

• [dpsliding]
• [dpwalkback]

连续价值背包

通常您需要具有固定精度才能计算最佳解决方案。浮点数有太多的精度。您可能可以使用 dpwalkback 来解决这个问题，但如果有许多物品，则不行。

一种替代方法是使用概率来找到一个具有一定百分比拟合/成为最佳解决方案机会的解决方案。

• [连续]

测试

理想情况下，我们会有一个全面的测试套件，但这只是我的一个副项目 ;).

目前我只实现了同一种算法两次（使用递归/原始方法和优化的动态规划方法）。对这两种方法的模糊测试通常能揭示大多数实现问题。

如果您有关于如何可靠地测试 Rust 代码而不头疼的想法，我将欢迎任何证明概念的 PR :)

贡献

欢迎 PR 和错误修复！