seo网站优化报价,网站功能设计有哪些要求,网络广告的概念,苏州网站建立公司动态规划#xff1a;这种算法思想多用来求解最优化问题#xff0c;因此这里存在一个最优化法则#xff0c;法则指出最优化问题任一实例的最优解#xff0c;都是由其子实例的最优解构成的。一般来说#xff0c;自底向上的动态规划更容易设计#xff0c;但是带有记忆功能的…动态规划这种算法思想多用来求解最优化问题因此这里存在一个最优化法则法则指出最优化问题任一实例的最优解都是由其子实例的最优解构成的。一般来说自底向上的动态规划更容易设计但是带有记忆功能的自顶向下的动态规划跟能高效的解决问题尤其是针对重叠子的问题。
1、币值最大化问题给定一排n枚硬币面值为正整数c1c2...cn,面值可能相同请问如何选取硬币可以使得在其原始位置不相邻的条件下。所选币值总和最大。
思路我们可以将问题划分为取最后一枚硬币和不取最后一枚硬币。根据不相邻这一条件若取最后一枚硬币则我们继续判断前n-2枚硬币中的币值总和最大问题若不取最后一枚则我们继续判断前n-1枚硬币中的币值总和最大问题。
由此得到递推方程如下并且我们已知F(0) 0F(1) c1, Input:
6
5 1 2 10 6 2
Output:
17 import java.util.Scanner;public class Main {static int[] c new int[10];static int[] f new int[10];static Scanner in new Scanner(System.in);public static void main(String[] args) {int n in.nextInt();for (int i 1; i n; i) {c[i] in.nextInt();}System.out.println(coinRow(n));}private static int coinRow(int n) {f[0] 0;f[1] c[1];for (int i 2; i n; i) {f[i] Math.max(c[i] f[i-2], f[i-1]);}return f[n];}
}
我们在这个过程中不仅得出了最大金额为17我们在f[]中也可以求得前i枚硬币1i6的最大金额。时间复杂度和空间复杂度均为O(n)。 2、找零问题假设我们需要找零的金额为n至少需要多少面值为d1d2...dm的硬币其中d1 1且每种面值的硬币无限制。
思路我们可以理解获得n的途径为在总金额为n-dj的一堆硬币中在找一枚面值为dj的硬币其中j1,2...,m且ndj。因此找到一个满足要求的dj使得F(n-dj) 1最小的dj即可。由于1是常量所以我们需要专注寻找一个最小的F(d-dj)。
由此得到的递推公式如下且一直F(0) 0 Input:
6
1 3 4
Output:
2 import java.util.Scanner;public class Main {static int[] c new int[10];static int[] f new int[10];static int sum;static Scanner in new Scanner(System.in);public static void main(String[] args) {sum in.nextInt();int n in.nextInt();c[1] 1;for (int i 2; i n; i) {c[i] in.nextInt();}System.out.println(changeMaking(n));}private static int changeMaking(int n) {for (int i 1; i sum; i) {int temp 99999999;int j 1;while (j n i c[j]) {temp Math.min(f[i-c[j]], temp);j;}f[i] temp 1;}return f[sum];}
}
3、硬币收集问题在n*m格模板中放有一些硬币每格的硬币数目最多为一个。从左上方开始收集尽可能收集多的硬币直到右下角对于每个单元格来说只能取对应右边一格或者下边一格的硬币。试求出最大的硬币数及相应的路径。思路我们假设F(i, j)为行走到(i, j)所能收集到的最大硬币数。单元格(i, j)可以经由上方(i-1, j)和左侧单元格(i, j-1)到达。单元格(i-1 ,j)对应的最大硬币数为F(i-1, j)(i, j-1)对应的最大硬币数为F(i, j - 1)。当然第一行单元格上方没有单元格第一列单元格左边没有单元格即F(i-1, j) 0F(i, j-1) 0所以其递推公式为 Input:
5 6
0 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 1 0
Output:
5 import java.util.Scanner;public class Main {static int[][] c new int[10][10];static int[][] f new int[10][10];static int sum, n, m;static Scanner in new Scanner(System.in);public static void main(String[] args) {n in.nextInt();m in.nextInt();for (int i 1; i n; i) {for (int j 1; j m; j) {c[i][j] in.nextInt();}}f[1][1] c[1][1];System.out.println(coinCollection());}private static int coinCollection() {/*** 左上角初始位置* */f[1][1] c[1][1];/*** 第一列只有上方来的* */for (int i 2; i n; i) {f[i][1] f[i-1][1];}/*** 第一行只有左侧来的* */for (int j 2; j m; j) {f[1][j] f[1][j-1];}for (int i 2; i n; i) {for (int j 2; j m; j) {f[i][j] Math.max(f[i-1][j], f[i][j-1]) c[i][j];}}return f[n][m];}
}
