一个例子
1.描述
image.png
对于方程的描述
1.当物品或者容量某一项为空,装入的最大价值都为0
2.当遍历到第i类商品的重量大于给出的容量时,是无法装入第i类商品,因此沿用上一个过程的装入策略 即:w[i] > j v[i][j] = v[i-1][j]
3.当遍历到第i类商品的重量是小于给出的容量时,就可以装入第i类商品,理解v[i-1][j-w[i]]
装入前i-1类商品到剩余的空间(容量)-->j-wi,->解释是在剩余空间下i-1中类型商品情况下的选择策略 max{}理解为比较与上一个策略的容量,要此次策略要采取的..
public class DynamicProgramming {
/*01背包问题
* 分别有三个物品 要存放到背包(重量为4)中 计算最大的价值
* 重量:1 4 3
* 价值:1500 3000 2000
* 动态规划例题
* */
public static void main(String[] args) {
int[] hight = new int[]{1, 2, 3};
int[] value = new int[]{1500, 3000, 2000};
int n = 4;//背包的容量
int m = value.length;//物品的个数
//设置一个二维数组表示总价值 加一表示 物品或者容量为0情况
int[][] val = new int[m + 1][n + 1];
for (int i = 0; i < val.length; i++) {
val[i][0] = 0;
}
for (int i = 0; i < val[0].length; i++) {
val[0][i] = 0;
}
for (int i = 1; i < val.length; i++) {
for (int j = 1; j < val[0].length; j++) {
if (hight[i - 1] > j) {
//采用上一个的策略
val[i][j] = val[i - 1][j];
} else {
//对该函数的说明 val[i-1][j-hight[i]] 第i个商品的剩余容量
val[i][j] = Math.max(val[i - 1][j], value[i - 1] + val[i - 1][j - hight[i - 1]]);
//value[i] 是必定能取到的 后一个[j-hight[i]]剩余的空间,后一个的描述是,只有
//[j-hight[i]]空间 遍历到val[i]种类型的选择策略
//商品的类型是不断增加的
//原来函数的标准式:val[i][j] = Math.max(val[i-1][j] , value[i] + val[i-1][j-hight[i]])
}
}
}
//遍历
for (int i = 0; i < val.length; i++) {
for (int i1 = 0; i1 < val[0].length; i1++) {
System.out.print(Integer.toString(val[i][i1]) + " ");
}
System.out.println();
}
}
}
一个例题:关于动态规划和递归法
public class ClimbStairs {
/**
* Created with IntelliJ IDEA.
* Description:
* User: tongyongtao
* Date: 2020-10-11
* Time: 20:27
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
* f(x)=f(x−1)+f(x−2)
* 动态规划和递归法的区别: 自下而上 自上而下
* 注意滚动数组的应用
*/
public static void main(String[] args) {
climbStairs(12);
System.out.println(climbStairs1(12));
System.out.println(climbStairs2(12));
System.out.println(climbStairs3(12));
}
//滚动数组方法
public static void climbStairs(int n) {
//f(0)=1
int p = 0;
int q = 0;
int r = 1;
for (int i = 0; i < n; ++i) {
p = q;
q = r;
r = p + q;
}
System.out.println(r);
}
//动态规划算法
public static int climbStairs1(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
//dp的优化
public static int climbStairs2(int n) {
int prev = 1;
int cur = 1;
for (int i = 2; i < n + 1; i++) {
//tmp只是一个临时变量,用来存储cur的值,然后赋值给prev
int tmp = cur;
cur = prev + cur;
prev = tmp;
}
return cur;
}
//递归
public static int climbStairs3(int ints) {
if (ints <= 2) {
return ints;
}
return climbStairs3(ints - 1) + climbStairs3(ints - 2);
}
}
一个例题:体会方程的构建
public class MaxSubArray {
/*
* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组
* （子数组最少包含一个元素），返回其最大和
*
*
* 思想:相加数组中的所有元素,直到遇到一个比这个和还要大的元素,舍弃这个和,重新求和,反复进行
* */
public static void main(String[] args) {
int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
maxSubArray1(nums);
maxSubArray2(nums);
}
//f(i)=max{f(i−1)+a 转移方程 滚动思想
public static void maxSubArray1(int[] ints) {
//索引 0-ints.lenth
//用来接收和
if (ints.length==0){return;}
int sum = 0;
//最大的值
int max = ints[0];
for (int x : ints) {
//转移方程,如果前面的和小于x,则舍弃前面的所有数
sum = Math.max(sum + x, x);
//比较与赋值
max = Math.max(sum, max);
}
System.out.println(max);
}
//动态规划
public static void maxSubArray2(int[] ints) {
//数组的长度
int length = ints.length;
//构建一个dp存放以ints[i]为结尾最大子序
int[] dp = new int[length];
dp[0] = ints[0];
for (int i = 1; i < length; i++) {
// 取当前元素的值 和 当前元素的值加上一次结果的值中最大数
dp[i] = Math.max(ints[i], dp[i - 1] + ints[i]);
}
//遍历dp数据获取最大的最大子序
int max = 0;
for (int x : dp) {
max = Math.max(max, x);
}
System.out.println(max);
}
}
背包问题的优化
public class DynamicProgramming1 {
/**
* Created with IntelliJ IDEA.
* Description:
* User: tongyongtao
* Date: 2020-10-12
* Time: 19:16
* 重量:1 4 3
* 价值:1500 3000 2000
* 优化求出最后结果
*/
public static void main(String[] args) {
//存储每种商品的重量
int[] weight = new int[]{1, 4, 3};
//存储每种商品的价格
int[] value = new int[]{1500, 3000, 2000};
//背包的容量是4
int n = 4;
//构建一个二维数组用来表示每次选择的价值
int[][] val = new int[weight.length + 1][n + 1];
//初始化val[][0] val[0][];
for (int i = 0; i < val.length; i++) {
val[i][0] = 0;
}
for (int i = 0; i < val[0].length; i++) {
val[0][i] = 0;
}
//由于第一行和第一列都进行的赋值,所以从1开始遍历
//假设第i个商品的重量是大于本次的容量的则采取上一次的策略
//如果是小于本次容量的则进行比较 //上一次的策略和本次可以容纳的策略
//构建方程 max{val[i-1][j] , value[i] + val[i-1][j - weight[i]] }
//建一个数组来记录信息
int[][] path = new int[value.length + 1][n + 1];
for (int i = 1; i < val.length; i++) {
//容量每次递增
for (int j = 1; j < val[0].length; j++) {
//本次商品种类的重量是大于本次的容量的,选择的策略是上一次的
//此处索引从1开始的
if (weight[i - 1] > j) {
val[i][j] = val[i - 1][j];
}
/* else {
//是可以采用本次商品的,策略是与上一次进行比较
val[i][j] = Math.max(val[i-1][j] , value[i-1] +val[i-1][j -weight[i-1]] );
}*/
else if (val[i - 1][j] < value[i - 1] + val[i - 1][j - weight[i - 1]]) {
val[i][j] = value[i - 1] + val[i - 1][j - weight[i - 1]];
path[i][j] = 1;
} else {
val[i][j] = 1;
}
}
}
for (int i = 0; i < val.length; i++) {
for (int j = 0; j < val[0].length; j++) {
System.out.print(val[i][j]);
}
System.out.println();
}
//从上往下遍历获取最后一次的背包存储情况
int i = path.length - 1;
int j = path[0].length - 1;
while (i > 0 && j > 0) {
if (path[i][j] == 1) {
//索引从一开始
System.out.printf("%d放入背包", i);
//背包的容量被占据
j -= weight[i - 1];
}
i--;
}
}
}
