algorithm-ta-tutorial：作为南京大学“算法设计与分析”课程的技术援助之一提供的指南
2023-09-07 08:50:20
319.42MB
1
本文介绍了多维背包问题的算法设计与分析。多维背包问题是在经典的 0-1 背包问题上增加了一个维度，要求物品的所有属性在满足对应约束条件的情况下，获取到背包的最大价值。本文提出了利用回溯法解决多维背包问题的方法，将多维背包问题转化为子集选取问题，适合用子集树表示解空间。在搜索解空间树时，只要左儿子节点是可行节点，搜索就进入左子树，在右子树中可能含有最优解时才进入右子树搜索。否则将右子树剪去。
2023-05-17 17:47:21
53KB
1