8.11 动态规划例题-----钢条切割(从递归--＞记忆型递归----＞动态规划)

本文主要是介绍8.11 动态规划例题-----钢条切割(从递归--＞记忆型递归----＞动态规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

已知钢条总长i 和每种长度下的钢条价格，让我们找到一种切割方案，使得价格最大

解法一：递归


import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：假设钢条长度为L* 依次固定前面的切割点为1....L,计算最大价值* * 测试数据
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30* */static int L;//钢条长度static int[] ls;//钢条的长度static int[] ps;//对应长度下的价格public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);L= sc.nextInt();ls = new int[L];ps = new int[L];for(int i=0;i<L;i++) {//输入钢条长度ls[i]=sc.nextInt();}for(int i=0;i<L;i++) {//输入对应长度下的价格ps[i]=sc.nextInt();}int ans = dfs(L);//从最大长度开始System.out.println(ans);}private static int dfs(int k) {//当前剩余钢条的长度kif(k==0) {//遍历完所有长度return 0;}int ans=0;for(int i=1;i<=k;i++) {//从剩余长度中依次选择长度1...K。对应的下标为i-1int v = ps[i-1]+dfs(k-i); //截取长度i，从剩余的k-i长度中继续查找ans = Math.max(ans, v);}return ans;}	
}

解法二：记忆型递归


import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：假设钢条长度为L* 依次固定前面的切割点为1....L,计算最大价值*改进：添加数组rem，用来记录每种剩余长度下的最大价值* * 测试数据
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30* */static int L;//钢条长度static int[] ls;//钢条的长度static int[] ps;//对应长度下的价格static int[] rem;//记忆数组public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);L= sc.nextInt();ls = new int[L];ps = new int[L];for(int i=0;i<L;i++) {//输入钢条长度ls[i]=sc.nextInt();}for(int i=0;i<L;i++) {//输入对应长度下的价格ps[i]=sc.nextInt();}//初始化remrem = new int[L];for(int i=0;i<L;i++) {rem[i]=-1;}int ans = dfs(L);//从最大长度开始System.out.println(ans);}private static int dfs(int k) {//当前剩余钢条的长度kif(k==0) {//遍历完所有长度return 0;}//（1）计算之前先查找if(rem[k-1]>=0) {return rem[k-1];}//(2)计算int ans=0;for(int i=1;i<=k;i++) {//从剩余长度中依次选择长度1...K。对应的下标为i-1int v = ps[i-1]+dfs(k-i); //截取长度i，从剩余的k-i长度中继续查找ans = Math.max(ans, v);}//（3）计算之后记录rem[k-1] = ans;return ans;}	
}

解法三：动态规划

代码：


import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：动态规划* * 测试数据
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30* */static int L;//钢条长度static int[] ls;//钢条的长度static int[] ps;//对应长度下的价格static int[] dp;//存放每种长度下，最大价值public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);L= sc.nextInt();ls = new int[L];ps = new int[L];for(int i=0;i<L;i++) {//输入钢条长度ls[i]=sc.nextInt();}for(int i=0;i<L;i++) {//输入对应长度下的价格ps[i]=sc.nextInt();}//（2）动态规划dp = new int[L+1];dp[0]=0;//长度为0时，价值为0for(int i=1;i<=L;i++) {//钢条长度int ans=0;for(int j=1;j<=i;j++) {//长度i下，固定长度jans = Math.max(ps[j-1]+dp[i-j], ans); //固定长度j的价格 + （总长度i-固定长度j）的最大价值}dp[i]=ans;}//(3)输出结果System.out.println(dp[L]);}	
}