搜搜做题作业网请搞数学建模或者ACM的人给点思路
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：数学作业 时间：2024/07/27 15:15:19
请搞数学建模或者ACM的人给点思路
假设要缝制一面大旗,大小为w*h,现在有一系列的大小分别为w1*h1,w2*h2,……,wi*hi,……,wn*hn的n种布料块(w1
布料块必须买整块，不允许裁剪后再买。
“布料块可以横向或竖向裁剪（不允许斜切）”是指买好布料块之后制作大旗的时候，可以裁切布料块。一块布料块被裁切下来的部分不允许用在别处。
假设要缝制一面大旗,大小为w*h,现在有一系列的大小分别为w1*h1,w2*h2,……,wi*hi,……,wn*hn的n种布料块(w1
布料块必须买整块，不允许裁剪后再买。
“布料块可以横向或竖向裁剪（不允许斜切）”是指买好布料块之后制作大旗的时候，可以裁切布料块。一块布料块被裁切下来的部分不允许用在别处。
dp[i][j]代表组成高为j,宽为i的旗子的最少花费.
dp[i][j]=min{min{dp[i-w[t]][j]][j]+p[t]},min{dp[i][j-w[k]]+p[k]}}
算法复杂度为
O（W*H*（W+H）*N）
再问： dp[i-w[t]][j]][j] 这里是不是多了个中括号？ 还有dp[i][j]既然为最小花费了，还没有计算出来，怎么能参与计算呢？ 多谢英雄作答，如果能给出具体思路或者代码的话，我愿意继续追加100分。
再答： 你的理解是对的。 初值和递推方程都有了，程序很好写的。
dp[i][j]=min{min{dp[i-w[t]][j]][j]+p[t]},min{dp[i][j-w[k]]+p[k]}}
算法复杂度为
O（W*H*（W+H）*N）
再问： dp[i-w[t]][j]][j] 这里是不是多了个中括号？ 还有dp[i][j]既然为最小花费了，还没有计算出来，怎么能参与计算呢？ 多谢英雄作答，如果能给出具体思路或者代码的话，我愿意继续追加100分。
再答： 你的理解是对的。 初值和递推方程都有了，程序很好写的。