Java教程

动态规划之背包问题(java)

本文主要是介绍动态规划之背包问题(java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、动态规划

  动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。

二、基本思想

  (1)将大问题划分为小问题进行解决,从而一步步获得最优解;
  (2)动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
  (3)与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。(即下一次求解是在上一次得到的最优解基础上进行的)
  (4)可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。具体的动态规划算法多种多样,但它们具有相同的填表格式。

三、简单实例(背包问题)

  (1)背包问题:有一个容量为4磅的背包,现有以下物品

物品重量(磅)价格($)
吉他(G)11500
音响(S)43000
电脑(L)32000

  求在容量允许下能够装入放入最大价值是多少?(每个物品只能装入一次)
  (2) 解题思路:
  利用动态规划,每次遍历到的第i个物品,根据 w [ i − 1 ] w[i-1] w[i−1]和 v a l [ i − 1 ] val[i-1] val[i−1]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设 v a l [ i − 1 ] val[i-1] val[i−1]、 w [ i − 1 ] w[i-1] w[i−1]分别为第i个物品的价值和重量(这里 i − 1 i-1 i−1是因为数组下标的原因),M为背包的容量。再令 v [ i ] [ j ] v[i][j] v[i][j]表示在前 i i i个物品中能够装入容量为 j j j的背包中的最大价值。则我们有下面的结果:

第一步:初始化v[i][0]=v[0][i]=0;//表示填入表第一行和第一列是0;
第二步:当w[i]>j时: v[i][j]=v[i-1][j]//当准备加入新增的商品的容量大于当前背包的容量时,就直接使用上一个单元格的装入策略;
第三步:当j>=w[i]时:v[i][j]=max{v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]}//当准备加入的新增的商品的容量小于等于当前背包的容量,v[i-1][j]:就是上一个单元格的装入的最大值,val[i-1]:表示当前商品的价值,v[i-1][j-w[i-1]]:装入第i-1个物品,剩余的空间可装入的最优解。

  (3)动态规划图表:

0磅1磅2磅3磅4磅
00000
吉他(G)01500150015001500
音响(S)01500150015003000
电脑(L)01500150020003500

  (4)代码实现:

package com.haiyang.algorithm.dp;

/**
 * @author haiYang
 * @create 2022-01-28 16:33
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = new int[]{1, 4, 3};//物品重量
        int[] val = new int[]{1500, 3000, 2000};//物品价格
        int m = 4;//背包容量
        int n = val.length;//物品个数

        int[][] v = new int[n + 1][m + 1];//记录前i个物品中能够装入容量为j的背包中的最大值
        int[][] path = new int[n + 1][m + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                if (w[i - 1] > j) {//w[i-1]:第i个物品的数组下标为i-1,当第i个物品的重量大于背包容量,表示装不下这个物品,因此最大值为v[i-1][j]
                    v[i][j] = v[i - 1][j];
                } else {
                    //val[i-1] + v[i-1][j-w[i-1]]:表示装入第i-1个物品的价值加上剩余空间能够装的最大价值
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;//标记该物品加入背包,便于查看那些物品加入背包
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }

        }
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[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.println("第" + i + "个物品加入背包!");
                j = j - w[i - 1];
            }
            i--;
        }
    }
}

这篇关于动态规划之背包问题(java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!