JAVA算法：切割木棒—递归算法与动态规划算法

JAVA算法：切割木棒—递归算法与动态规划算法

给定一根长度为N的木棒和一系列价格，其中包含所有小于N的尺寸的价格。通过切割木棒和出售木棒来确定可获得的最大值。

例如，如果木棒的长度为8，不同部分的值如下所示，则可获得的最大值为22（通过切割两段长度2和6）

使用动态规划解决这个问题。

最优子结构

通过在不同的位置进行切割并比较切割后获得的值来获得最佳价格。

对于长度为n的木棒，将CutRod(n)设为所需（可能的最佳价格）值。CutRod(n)可以定义为：

CutRod(n) = Max（价格[i]+CutRod(n-i-1)）for all i in {0，1..N-1}

重叠的子问题

下面是切割木棒问题的简单递归实现。实现只遵循上面提到的递归结构。

算法设计

package com.bean.algorithm.basic;public class RodCutting {// A Naive recursive solution for Rod cutting problem/** Returns the best obtainable price for a rod of length n and price[] as prices* of different pieces*/static int cutRod(int price[], int n) {if (n <= 0)return 0;int max_val = Integer.MIN_VALUE;// Recursively cut the rod in different pieces and// compare different configurationsfor (int i = 0; i < n; i++)max_val = Math.max(max_val, price[i] + cutRod(price, n - i - 1));return max_val;}/* Driver program to test above functions */public static void main(String args[]) {int arr[] = new int[] { 1, 5, 8, 9, 10, 17, 17, 20 };int size = arr.length;System.out.println("Maximum Obtainable Value is " + cutRod(arr, size));}
}

程序运行结果：

Maximum Obtainable Value is 22

考虑到上述实现过程，下面是长度为4的杆的递归调用过程（递归树）。

 在上述部分递归树中，CR（2）被求解两次。我们可以看到，有许多子问题是反复解决的。由于再次调用了相同的父问题，所以这个问题具有重叠的子族属性。因此，切割木棒问题具有动态规划问题的两个性质。与其他典型的动态规划（DP）问题一样，可以通过自下而上构造dp[]数组来避免相同子问题重复计算。

下面给出动态规划算法

package com.bean.algorithm.basic;public class RodCutting2 {/** A Dynamic Programming solution for Rod cutting problem* Returns the best obtainable price for a rod of length n and price[] as prices* of different pieces*/static int cutRod(int price[], int n) {int val[] = new int[n + 1];val[0] = 0;// Build the table val[] in bottom up manner and return// the last entry from the tablefor (int i = 1; i <= n; i++) {int max_val = Integer.MIN_VALUE;for (int j = 0; j < i; j++)max_val = Math.max(max_val, price[j] + val[i - j - 1]);val[i] = max_val;}return val[n];}/* Driver program to test above functions */public static void main(String args[]) {int arr[] = new int[] { 1, 5, 8, 9, 10, 17, 17, 20 };int size = arr.length;System.out.println("Maximum Obtainable Value is " + cutRod(arr, size));}
}

程序运行结果：

Maximum Obtainable Value is 22