python - 自顶向下棒切割动态规划
问题描述
您将如何使用自上而下的方法来解决杆切割问题,以便它返回长度为 [0 - 杆长度] 的所有杆的最大成本列表,并返回用于实现该最大成本的零件?我已经成功地实施了自下而上的方法。
def cutRod(pricelist):
length = len(pricelist)
r = [0] * length
s = [0] * length
for j in range(1, length):
maxVal = 0
for i in range(1, j + 1):
if maxVal < pricelist[i] + r[j - i]:
maxVal = pricelist[i] + r[j - i]
if pricelist[j - i] != 0:
s[j] = [i, j - i]
else:
s[j] = [i]
r[j] = maxVal
return r,s
但是通过自上而下的方法,这就是我所得到的
def cutRod(pricelist, cost, parts):
length = len(pricelist)
if length <= 0:
return [0, cost, parts]
maxVal = 0
for i in range(0, length):
w = pricelist[i]
x, cost, parts = cutRod(pricelist[:length - i - 1], cost, parts)
if maxVal < x + w:
maxVal = x + w
return [maxVal, cost, parts]
截至目前,此函数仅返回与列表大小相同长度的杆的最大成本。
解决方案
public static int cutRod(int arr[],int n,Integer memo[]){
if(n<=0)
return 0;
int max=Integer.MIN_VALUE;
if(memo[n]!=null)
return memo[n];
else{
for(int i=0;i<n;i++)
{
max=Math.max(max,arr[i]+cutRod(arr,n-i-1,memo));
}
memo[n]=max;
return memo[n];
}
}
这是java中自上而下的解决方案!
推荐阅读
- python - 如何从图像中提取信息
- r - 如何创建具有分组的多个最小和最大点的多面图
- java - 无法使用 jdbc 模板将 Spring Boot 与 Secured Kerberos 连接
- jquery - 模态不显示按钮
- c++ - 重载运算符 == 和多态性的好习惯?
- python - Numba 和二维 numpy 数组列表
- java - 将 Solrj 与基本身份验证一起使用时,出现错误“原因:java.net.SocketException:连接重置”
- html - Django Html页面渲染项目循环
- c# - EventAggregator 如何注册事件和订阅者并通知所有订阅者事件触发?
- apache-spark - ¿ MultilayerPerceptronClassifier - Spark - mllib 中的 maxIter 参数是什么?