01背包问题
有n个重量和价值分别为wi,vi的物品,从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。
1≤n≤100
1≤wi,vi≤100
1≤W≤10000
输入:
n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
W=5
输出:
7(选择第0,1,3号物品)
因为对每个物品只有选和不选两种情况,所以这个问题称为01背包。
分析
01背包问题就是 选和不选,每个子问题都有两个分支

其中包含 重叠子问题 所以我们用记忆性递归来优化
- 计算之前先查询
- 计算之后做记录
dp算法是dfs的逆过程 从小的子问题开始一步一步生产

关键点就是max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])
代码
package BlueCup.Eight_DP_greed;
import java.util.Arrays;
import static java.lang.Math.max;
public class dp背包问题 {//01背包问题
static int[] w = {2, 1, 3, 2};
static int[] v = {3, 2, 4, 2};
static int n = 4;//物品数量
static int W = 5;//承重极限
static int[][] rec;
public static void main(String[] args) {
//dp 做法
int ans = dfs(0, W);
System.out.println(ans);
//重叠子问题不重复求解
//计算之前做查询,计算之后做记录
rec = new int[n][W + 1];
for (int i = 0; i < n; i++) {
Arrays.fill(rec[i], -1);
}
ans = m(0, W);
System.out.println(ans);
//dp 做法
ans = dp(n, W);
System.out.println(ans);
}
/**
* DP大法 是dfs的逆过程
* 先算小范围 按已有的结果计算
* @param n
* @param W
* @return
*/
private static int dp(int n, int W) {
int[][] dp = new int[n][W + 1];//四组 0~W重量
//初始化
for (int i = 0; i < n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i < W + 1; i++) {
if (i >= w[0]) dp[0][i] = v[0];//可以容纳
else dp[0][i] = 0;
}
for (int i = 1; i < n; i++) {//物品编号
for (int j = 1; j < W + 1; j++) {//背包容量0~W
if (j >= w[i]) dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j]);
else dp[i][j] = dp[i - 1][j];//要不起 延用上次
}
}
return (dp[n - 1][W]);
}
/**
* O(2^n)
*
* @param i 第几个
* @param ww 可用重量
* @return
*/
private static int dfs(int i, int ww) {
if (ww <= 0) return 0;//装不进去
if (i == n) return 0;//没有可选的了
int v2 = dfs(i + 1, ww);//不选择当前物品
if (ww >= w[i]) {
int v1 = v[i] + dfs(i + 1, ww - w[i]);//选择当前问题
return max(v1, v2);
} else {
return v2;
}
}
/**
* 记忆型递归
*
* @param i
* @param ww
* @return
*/
private static int m(int i, int ww) {
if (i == n) return 0;
if (ww <= 0) return 0;
//计算之前先查询
if (rec[i][ww] != -1) return rec[i][ww];
int ans;
int v2 = m(i + 1, ww);
if (ww >= w[i]) {
int v1 = v[i] + m(i + 1, ww - w[i]);
ans = max(v1, v2);
} else {
ans = v2;
}
rec[i][ww] = ans;
return ans;
}
}
本文作者:Author: 寒光博客
文章标题:[LanQiao] 01背包问题 动态规划 三种解法 dfs dp 记忆型递归
本文地址:https://dxoca.cn/Algorithm/255.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/255.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。