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

[此贴子已经被作者于2007-10-28 17:59:01编辑过]

大家帮帮忙啊,谢谢~

算法DP
时间复杂度O(X*Y*(X+Y))
空间复杂度O(X*Y)

dp[i][j]= max{ max{dp[i][k]+dp[i][j-k]},max{dp[k][j]+dp[i-k][j]} , if(i==ai&& j==bi ||i==bi&& j==ai)ci , 0};
其中dp[i][j]=x表示长i宽j的布的最大产生价值
dp[i][j]可以采用对称矩阵压缩存储

能讲清楚的吗?

我认为我已经讲的很清楚了，再清楚就是写代码了

还是看得不是很明白啊,这是考试题目,帮帮忙啊,谢谢~!