当前位置 :
请搞数学建模或者ACM的人给点思路假设要缝制一面大旗,大小为w*h,现在有一系列的大小分别为w1*h1,w2*h2,……,wi*hi,……,wn*hn的n种布料块(w1布料块必须买整块,不允许裁剪后再买。“布料块可以
3人问答
更新时间:2024-05-05 00:14:26
问题描述:

请搞数学建模或者ACM的人给点思路

假设要缝制一面大旗,大小为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分。
郎国军回答:
  你的理解是对的。初值和递推方程都有了,程序很好写的。
数学推荐
最新更新
热门数学
PC端 | 移动端 | mip端
问答网(wenda2.com)汇总了汉语字典,新华字典,成语字典,组词,词语,在线查字典,中文字典,英汉字典,在线字典,康熙字典等等,是学生查询学习资料的好帮手,是老师教学的好助手。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。

邮箱:联系方式:

Copyright©2009-2021 问答网 wenda2.com 版权所有 闽ICP备2022000227号-1