我正在研究动态编程,我正在寻求解决以下问题,可以在http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf找到:
给你一块尺寸为X×Y的矩形布,其中X和Y是正整数,以及可以使用布制作的n个产品列表.对于[1,n]中的每个产品,您知道需要一个尺寸为ai by bi的矩形布料,并且该产品的最终销售价格为ci.假设ai,bi和ci都是正整数.你有一台机器可以将任何矩形布块水平或垂直切成两块.设计一种算法,找到切割X×Y布料的最佳策略,以便由最终产品制成的产品给出最大的销售价格总和.您可以根据需要自由制作给定产品的副本,如果需要,可以不制作任何副本.(来自Dasgupta,Papadimitriou和Vazirani的算法.)
看起来我们有一种二维背包问题,但我认为通过将权重视为矩形区域,可以用传统的背包算法解决它.这看起来像是一种合理的方法吗？
这是我正在学习的课程的编程作业,所以请仅包括概念性讨论和/或伪代码来说明想法.