算法思想之动态规划(七)——背包问题

前言

今天我们继续讨论经典的动态规划问题之背包问题。

背包问题

问题描述

一个背包有一定的承重capacity，有n件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。

问题分析

其实，这类问题和之前讨论的找零钱问题有相似之处。我们使用二维数组dp进行动态规划——代表了承重为的情况下放入前i个物品时的最大总价值。当时，即放入第一个物品时，则有：；当时，显然有 。当 且 时，那么，则有如下几种情况：
(1) 不放第个物品，总价值为；
(2) 放第个物品，总价值为，此时，需要。
综上，。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。

public class Backpack {
    public int maxValue(int[] w, int[] v, int n, int cap) {
        // write code here
        return core(w, v, n, cap);
    }

    public static int core(int[] w, int[] v, int n, int cap) {
        if (n == 0 || w.length == 0 || v.length == 0 || cap == 0) {
            return 0;
        }

        int[][] dp = new int[n][cap + 1];

        // 初始化第0行
        for (int i = 0; i < cap + 1; i++) {
            dp[0][i] = i >= w[0] ? v[0] : 0;
        }

        // 初始化第0列
        for (int i = 0; i < n; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < cap + 1; j++) {
                if (j >= w[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[n - 1][cap];
    }

    public static void main(String[] args) {
        Backpack backpack = new Backpack();
        int[] w = new int[]{16, 36, 25, 19, 26, 23};
        int[] v = new int[]{619, 363, 582, 163, 487, 344};
        int n = 6;
        int cap = 35;
        int res = backpack.maxValue(w, v, n, cap);
        System.out.println(res);
    }
}

其他经典问题

• 算法思想之动态规划(二)——最小路径和问题
• 算法思想之动态规划(三)——找零钱问题
• 算法思想之动态规划(四)——最长公共子序列问题
• 算法思想之动态规划(五)——最小编辑距离问题
• 算法思想之动态规划(六)——最长上升子序列问题

总结

通过前面几篇博文，我对经典的动态规划问题进行了整理。
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。