• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

经典算法:动态规划

武飞扬头像
正经程序员
帮助26

前言

动态规划是一种解决复杂问题的方法,关键思想是将大问题分解为一组更简单的子问题,只解决每个子问题一次,并使用基于内存的数据结构存储解决方案。每个子问题解决方案都以某种方式被索引。通常使用输入参数的值,用于查找。所以,当出现相同的子问题时,无需重新计算解决方案,而是查找以前计算的解决方案,从而节省计算时间,这种存储子问题解决方案的思想就成为动态规划。

 

在一张纸上写下“1 1 1 1 1 1 1 1 = ?

回答:"八!"

在左边在写下另一个“1 ”,等于多少?

回答:"九!"

你怎么算的这么快呢?

回答:"你刚刚只是又加了一"。

所以你不需要重新计算,因为你记得有八个!动态编程只是一种花哨的方式来表达记住一些东西以节省时间

动态规划经典问题:0-1背包问题

现在要出去旅游,整理出来一些物品,每个物品有两个属性,必要性和重量,书包的承重有限,要求是在满足书包承重的基础上,尽可能的装最需要的东西。每个物品只能装一个。

代码示例:

输入:
 
必要性 = [ 20, 5, 10, 40, 15, 25 ]\
重量 = [ 1, 2, 3, 8, 7, 4 ]\
int W = 10(W为书包的承重极限)

输出:背包装的必要性为 60
 
必要性 = 20   40 = 60
重量= 1   8 = 9 < W

递归

使用递归的思想来解决这个问题。 将当前的物品包含在背包中,并且福使用背包容量减少的剩余物品。如果容量变为负数,就不返回,或者返回负无穷。

最后,返回我们通过包含或排除当前项目得到的最大值。递归的基本情况是没有剩余物品,或者容量变为 0。

Java示例代码:

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // base case: 没有剩余项目或容量变为0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. 将当前物品“v[n]”放在背包中,并重复使用
        // 剩余物品'n-1'容量减少'W-W[n]`
 
        int include = v[n]   knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. 从背包中排除当前物品'v[n]',并重复使用
        // 剩余项目'n-1`
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // 返回通过包含或排除当前项得到的最大值
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // 输入的值,v:必要性,w:重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "  
                knapsack(v, w, v.length - 1, W));
    }
}

输出:
背包必要值为60

上述解决方案的时间复杂度是指数级的,并且在调用堆栈中占据空间。

上述解具有最优子结构,即可以从其子问题的最优解有效地构造最优解。它也有重叠的子问题,即问题可以分解成子问题,每个子问题重复几次。为了重用子问题解决方案,我们可以使用动态规划,其中子问题解决方案被存储而不是一遍一遍的计算。

动态规划(自顶向下)

示例:

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // base case: 没有剩余项目或容量变为0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. 将当前物品“v[n]”放在背包中,并重复使用
        // 剩余物品'n-1'容量减少'W-W[n]`
        int include = v[n]   knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. 从背包中排除当前物品'v[n]',并重复使用
        // 剩余项目`n-1`
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // 返回通过包含或排除当前项得到的最大值
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // 输入的值,v:必要性,w:重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "  
                knapsack(v, w, v.length - 1, W));
    }
}

输出:
背包必要值为60

上述自顶向下解决方案的时间复杂度为O(nW),需要O(nW)额外空间,其中n是输入中的物品总数,W是背包的容量。

我们也可以采用自下而上的方式解决这个问题。在自下而上的方法中,我们首先解决较小的子问题,然后从中解决较大的子问题。以下自下而上的方法T[i][j]为每个1 <= i <= n和计算 ,这是在权重小于或等于并使用最多第一项的项目时0 <= j <= W可以获得的最大值。使用较小值且已计算的值。。

动态规划(自下而上)

class Main
{
    public static int knapsack(int[] v, int[] w, int W)
    {
        // `T[i][j]`存储背包重量的最大值
        // 小于等于'j',仅考虑前'i'项。
        int[][] T = new int[v.length   1][W   1];
 
        for (int i = 1; i <= v.length; i  )
        {
            // 考虑从0到最大容量W的所有权重
            for (int j = 0; j <= W; j  )
            {
                // 如果'j-w[i-1]'为负,则不包括第i个元素
                if (w[i-1] > j) {
                    T[i][j] = T[i-1][j];
                }
                else {
                    // 通过排除或包含找到我们得到的最大值
                    // 第i项
                    T[i][j] = Integer.max(T[i-1][j], T[i-1][j-w[i-1]]   v[i-1]);
                }
            }
        }
 
        // 返回最大的值(必要性)
        return T[v.length][W];
    }
 
    public static void main(String[] args)
    {
        // 输入的值,v:必要性,w:重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "   knapsack(v, w, W));
    }
}

输出:
背包必要值为60

上述自下而上解决方案的时间复杂度为O(nW),需要O(nW)额外空间,其中n是输入中的物品总数,W是背包的容量。

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanfbeaa
系列文章
更多 icon
同类精品
更多 icon
继续加载