背包问题——装满背包的最高价格
标题描述
背包问题给定两个长度为N和[i]的数组，[i]分别表示物品i的重量和价值。给定一个正数bag，表示一个装有负载的袋子，里面的物品不能超过这个重量。返回可以装载的最大值。
强力递归问题求解
为了获得最大值，您实际上必须在每个项目中进行选择。
找到最佳的选择方案。
按这个思路，递归就是通过选择或者不选择某个产品来比较最大值。
递归已经出来了。
然后我们讨论了基本情况。
1. 数组超出范围，没有产品可供选择，必须是结束条件
2.背包内已无更多空间，需退回底盒。
现在我们有了递归结构和基本情况，让我们看一下代码。
代码演示
/**
* 获取最大值
* @param w
* @param v
* @param bag
* @return
*/
public static int maxValue(int[]w,int[]v,int bag){
//参数校验,题目中其实已经对数据限制了,
if (null == w || v == null || w.length != v.length || w.length == 0 || bag < 0 ){
return 0;
}
return process(w,v,0,bag);
}
/**
* 递归方法
* @param weights 不同商品重量
* @param values 商品价值 和重量一一对应
* @param index 下标值 代表要选第几号商品了
* @param bag 背包容量
* @return
*/
public static int process(int[]weights,int[]values,int index,int bag){
//base case 越界
if (index == weights.length){
return 0;
}
//返回-1 为了对无效选择做判断
if (bag < 0){
return -1;
}
//选和不选两个状态
//不选的情况
int p1 = process(weights,values,index + 1,bag);
//选的情况
int p2 = 0;
//选的情况
int next = process(weights,values,index + 1,bag - weights[index]);
// 返回 -1 代表 bag - weights[index] 这个选择是无效 的.
//也就是index 这个选择是无效的 就不能执行if 里面的
//也可以先判断bag - weights[index] < 0 来判断,小于0 就不进行递归
// 和利用返回值判断是一样的,随你心情
if (next != -1){
p2 = values[index] + next;
}
//选择最大值
return Math.max(p1,p2);
}
动态规划解题思路
动态规划实际上是递归过程的抽象。将递归放在一个表中
递归转化为动态规划：
首先，我们需要查看递归基本情况，以便知道如何初始化值。
接下来我们看一下递归过程。
下面的代码演示了
代码演示
/**
* 动态规划
* @param w
* @param v
* @param bag
* @return
*/
public static int dp(int[]w,int[]v,int bag){
//参数校验
if (null == w || v == null || w.length != v.length || w.length == 0 || bag < 0 ){
return 0;
}
int N = w.length;
//动态规划表
//初始化的过程 看递归的base case index == N 是0,
//数组本身就是0 因此不需要显示的初始化
int[][] dp = new int[N + 1][bag + 1];
//看递归过程,来决定如何改动态规划
//由于base case 是到N 开始返回的
//所以dp 要从N - 1 开始填充值.
//因此从N - 1开始循环
for (int i = N - 1;i >= 0;i--){
for (int k = 0; k <= bag;k++){
// int p1 = process(weights,values,index + 1,bag);
// 这一行代码 就是递归改动态规划,
int p1 = dp[i + 1][k];
//选的情况
int p2 = 0;
// int next = process(weights,values,index + 1,bag - weights[index]);
// 看下两着是不是一样 只是一个递归 一个表中取.
int next = bag - w[i] < 0 ? -1 : dp[i + 1][bag - w[i]];
if (next != -1){
p2 = v[i] + next;
}
dp[i][k] = Math.max(p1,p2);
}
}
return dp[0][bag];
}
动态规划
纸牌游戏问题 – 动态规划
爬楼梯问题——从强力递归到动态规划
有多少种方法可以到达特定位置？——从强力递归到动态规划
硬币交换、硬币收集问题，从蛮力递归到动态规划
斐波那契数列 - 从强力递归到动态规划