美文网首页
算法理论 | 动态规划

算法理论 | 动态规划

作者: icebreakeros | 来源:发表于2019-08-03 11:13 被阅读0次

动态规划

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的

应用场景

适用动态规划的问题必须满足最优化原理、无后效性和重叠性

实例

背包问题

前面提到贪心算法不能解决0-1背包问题,我们可以使用动态规划解决

问题描述:0-1背包问题,将重量为(w1,w2,w3,w4,w5...)、价值为(v1,v2,v3,v4,v5...)的物品放入容量为N的背包中,怎样放价值最大

思路:
v[i][j]为放入前i个物品到容量为j的背包中的最大值,i一定是小于物品总个数的,j一定是小于N
则有等式:
v[0][j] = v[j][0] = 0
if (w[i] > j) { v[i][j] = v[i-1][j] }
if (w[i] <= j) { v[i][j] = Max(v[i-1][j], v[i-1][j-w[i]] + value[i]) }

public class PackageProblem {

    public int maxVaule(int[] weight, int[] value, int capacity) {
        int wl = weight.length;
        int vl = capacity + 1;
        int maxValue = 0;
        int[][] v = new int[wl][vl];
        for (int i = 0; i < wl; i++) {
            for (int j = 0; j < vl; j++) {
                if (i == 0) {
                    v[i][j] = 0;
                } else if (j == 0) {
                    v[i][j] = 0;
                } else {
                    if (weight[i] > j) {
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = Math.max(v[i - 1][j], 
                            v[i - 1][j - weight[i]] + value[i]);
                    }
                    maxValue = v[i][j];
                }
            }
        }
        print(v);
        return maxValue;
    }

    private void print(int[][] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers[0].length; j++) {
                System.out.printf("%d\t", numbers[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        PackageProblem packageProblem = new PackageProblem();
        int[] weight = new int[]{7, 3 ,4, 5};
        int[] value = new int[]{42, 12, 40, 25};
        int capacity = 10;
        int result = packageProblem.maxVaule(weight, value, capacity);
        System.out.println(result);
    }
}

相关文章

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画:什么是动态规划?3.算法之动态规划4. 动态规划-算法

  • Swift 算法实战:动态规划

    Swift 算法实战:动态规划 Swift 算法实战:动态规划

  • 算法理论 | 动态规划

    动态规划 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的...

  • 程序员算法基础——动态规划

    程序员算法基础——动态规划 程序员算法基础——动态规划

  • 动态规划

    --tags: 算法,动态规划 动态规划解题 引入:动态规划 和贪心法 都是算法的思想方法 贪心算法——像 第一类...

  • 动态规划 Dynamic Programming

    从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...

  • 动态规划-js

    动态规划 参考:算法分析与设计-贪心&动归 漫画:什么是动态规划? 【数据结构与算法】 DP 动态规划 介绍 介绍...

  • 动态规划

    动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...

  • 2018-11-14

    今天学了动态规划一些知识,着重看了一下动态规划之背包算法(主要是0-1算法和部分算法),关于动态规划的问题重点是建...

  • 动态规划

    算法-动态规划 Dynamic Programming

网友评论

      本文标题:算法理论 | 动态规划

      本文链接:https://www.haomeiwen.com/subject/zsvkdctx.html