霍红卫习题3-20 剪裁问题

给定长、宽各为X、Y矩形布，其中X、Y为正整数，以及可用这块布制造的n个产品。对于每个产品i∈{1，2，…n},已知制造这个产品所需的布量，即ai*bi的一块矩形布和它的售价ci。假定ai,bi,ci是正整数。你有一台机器可以将一块矩形布水平或者垂直分成两快矩形布。对于给定的一块布，试设计一算法找出每个产品制造的数量（0、1或更多），使的总销售价格最大。（i为下标）
要求:
(1)给出整个思考分析过程
(2)最优子结构的刻画
(3)伪代码(加注释说明)
(4)时间,空间复杂度分析
(5)完整的C语言代码