栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构(Java)动态规划(0-1背包问题)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构(Java)动态规划(0-1背包问题)

一、介绍 1) 动态规划 ( Dynamic Programming ) 算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 ● 2) 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 ● 3) 与分治法不同的是, 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 ) ● 4) 动态规划可以通过 填表的方式 来逐步推进,得到最优解 .

二、动态规划算法最佳实践-背包问题

背包问题:有一个背包,容量为4磅 , 现有如下物品

物品

重量

价格

Uzi

1

1500

98K

4

3000

Akm

3

2000

1) 要求达到的目标为装入的背包的总价值最大,并且重量不超出 2) 要求装入的物品不能重复 3) 思路分析和图解         算法的主要思想,利用动态规划来解决。每次遍历到的第i 个物品,根据 w[ i ] 和 v[ i ] 来确定是否需要将该物品放入背包中。即对于给定的 n 个物品,设 v[ i ] 、 w[ i ] 分别为第 i 个物品的价值和重量, C 为背包的容量。再令 v[ i ][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果:

(1)  v[ i ][0]=v[0][j]=0; // 表示 填入表 第一行和第一列是 0

      (2) 当w[i]> j 时:v[i][j]=v[i-1][j]  

       // 当准备加入新增商品的容量大于 当前背包的容量时,就直接使用上一个单元格的装入策略

      (3) 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}  

        // 当 准备加入的新增的商品的容量小于等于当前背包的容量,

        // 装入的方式:先把新的装进去,如果有剩余空间的话尽可能装价值大的

        v[i-1][j]: 就是上一个单元格的装入的最大值

        v[i] : 表示当前商品的价值

        v[i-1][j-w[i]] : 装入i-1商品,到剩余空间j-w[i]的最大值

        当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :

三、代码演示

1.物品类

class thing{
    private String name;//物品名字
    private int weight;//物品重量
    private int value;//物品价值

    public thing(String name, int weight, int value) {
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return  name + "     "  + weight+ "     " + value;
    }
}

2.主程序

  public static void main(String[] args) {
        int maxVolume = 8;//背包容量:8
        //物品栏
        List items = new ArrayList<>();
        items.add(new thing("000", 0, 0));//用来占位置的,没实际意义
        items.add(new thing("Uzi", 1, 1500));
        items.add(new thing("98k", 4, 3000));
        items.add(new thing("Akm", 3, 2000));
        //先看下物品栏有哪些东西
        System.out.println("物品    重量    价格");
        for (thing e : items) System.out.println(e);
        System.out.println();
        //对于不同物品、不同背包容量,能够装入背包的物品的最大价值
        int[][] values = new int[items.size()][maxVolume+1];
        //初始化.第一列/行置0
        for (int i = 0; i < items.size(); i++) values[i][0] = 0;
        for (int i = 0; i < maxVolume+1; i++) values[0][i] = 0;

        //依次看装入(1),(1、2),(1、2、3)这几个物品时的情况
        for (int itemIndex = 1; itemIndex < items.size(); itemIndex++) {
            //依次看不同背包容量下的情况(1~8)
            for (int volume = 1; volume < maxVolume+1; volume++) {
                //1、如果准备加入的新物品容量比背包容量大,装不下新物品,
                //就使用同背包容量上次的装入策略
                if (items.get(itemIndex).getWeight() > volume) values[itemIndex][volume] = values[itemIndex - 1][volume];

                //2、否则就有两种情况
                    //2.1 加入新物品后,新物品价值加上剩余空间所放旧物品的最高价值
                    //比同背包容量上个装入策略的总价值要高,那我们就使用新的策略
                else if (values[itemIndex - 1][volume] < items.get(itemIndex).getValue() + values[itemIndex - 1][volume - items.get(itemIndex).getWeight()]) {
                    values[itemIndex][volume] = items.get(itemIndex).getValue() + values[itemIndex - 1][volume - items.get(itemIndex).getWeight()];
                }
                //2.2 否则还使用原来的策略。
                else {
                    values[itemIndex][volume] = values[itemIndex - 1][volume];
                }
            }
        }
        //看一下values 目前的情况,打印成表格
        System.out.print("物品/容量 ");
        for (int i = 1; i < maxVolume+1; i++) System.out.print(i + "     ");
        System.out.println();
        for (int i = 1; i < items.size(); i++) {
            System.out.print(items.get(i).getName() + "    ");
            for (int j = 1; j < maxVolume+1; j++) {
                System.out.print(values[i][j] + "  ");
            }
            System.out.println();
        }
    }

3.测试

物品    重量    价格
000     0     0
Uzi     1     1500
98k     4     3000
Akm     3     2000

物品/背包容量    1     2     3     4     5     6     7     8     
Uzi            1500  1500  1500  1500  1500  1500  1500  1500  
98k            1500  1500  1500  3000  4500  4500  4500  4500  
Akm            1500  1500  2000  3500  4500  4500  5000  6500  

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948891.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号