寒光博客

[LanQiao] 01背包问题 动态规划 三种解法 dfs dp 记忆型递归
01背包问题 有n个重量和价值分别为wi,vi的物品,从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值...
扫描右侧二维码阅读全文
19
2019/08

[LanQiao] 01背包问题 动态规划 三种解法 dfs dp 记忆型递归

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 (寒光博客)”原创,转载请保留文章出处。
Last modification:August 19th, 2019 at 08:57 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment