精华内容
下载资源
问答
  • 动态规划 01背包问题 滚动数组 C++实现 相关内容 动态规划 01背包问题 C++实现 01背包问题 有n中物品,每种只有一个,第i中物品的体积为Vi,重量为Wi,可以选择这些物品放入背包或者不放入背包,是的背包内物品在...

    动态规划 01背包问题 滚动数组 C++实现

    相关内容

    动态规划 01背包问题 C++实现

    01背包问题

    有n中物品,每种只有一个,第i中物品的体积为Vi,重量为Wi,可以选择这些物品放入背包或者不放入背包,是的背包内物品在总体积不超过容量capacity的前提下重量尽量大

    算法思想

    动态转移方程为d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);d[currentCapacity]表示将选取的前i个物品装入容量为currenCapacity的背包中的所能达到的最大总重量,d[currentCapacity - items[i].volume] + items[i].weight表示选取前i-1个物品装入容量为currentCapacity- items[i].volume的背包得到的最大重量加上当前物品的重量,其中currentCapacity减去items[i].volume,即减去了当前物品的体积,保证在背包容量能够容纳当前物品的情况下选取,d[currentCapacity - items[i].volume]的值为选取前i-1个物品装入容量为currentCapacity- item[i].volume的背包中最大重量(已经在上一个阶段计算出来),对于每个物品装入不同容量的背包中的情况,从背包最大容量capacity0从右往左计算,则在利用动态转移方程计算当前对应d数组值时,d[currentCapacity - items[i].volume]还是上一个状态的值没有改变,若左往右计算则会改变,导致得到意料之外的结果。

    int Knapsack::dynamicProgramming() {
        for (int i = 0; i < d.size(); i++) {
            d[i] = 0;
        }
        for (int i = 0; i < items.size(); i++) {
            for (int currentCapacity = capacity; currentCapacity >= 0; currentCapacity--) {
                if (currentCapacity >= items[i].volume) {
                    d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);
                }
            }
        }
    
        return d[capacity];
    }
    

    样例图解

    从右往左计算,计算d数组对应值时,前面的d[currentCapacity - items[i].volume]未被更改可以直接使用,将二维数组降低到一维,利用滚动数组减少内存开销,但只有最后一个状态的值
    在这里插入图片描述

    实现代码

    /*
    author : eclipse
    email  : eclipsecs@qq.com
    time   : Tue Jun 16 11:57:03 2020
    */
    #include <bits/stdc++.h>
    using namespace std;
    
    struct Item {
        int volume;
        int weight;
    };
    
    class Knapsack {
    private:
        vector<int > d;
        vector<Item> items;
        int capacity;
    public:
        Knapsack(vector<Item>& items, int capacity);
        int dynamicProgramming();
    };
    
    Knapsack::Knapsack(vector<Item>& items, int capacity) {
        this->items.insert(this->items.begin(), items.begin(), items.end());
        this->capacity = capacity;
        d.resize(capacity + 1);
    }
    
    int Knapsack::dynamicProgramming() {
        for (int i = 0; i < d.size(); i++) {
            d[i] = 0;
        }
        for (int i = 0; i < items.size(); i++) {
            for (int currentCapacity = capacity; currentCapacity >= 0; currentCapacity--) {
                if (currentCapacity >= items[i].volume) {
                    d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);
                }
            }
        }
    
        return d[capacity];
    }
    
    int main(int argc, char const *argv[]) {
        vector<Item> items;
        int N, capacity;
        scanf("%d%d", &N, &capacity);
        for (int i = 0; i < N; i++) {
            int volume, weight;
            scanf("%d%d", &volume, &weight);
            items.push_back((Item) {volume, weight});
        }
        Knapsack *knapsack = new Knapsack(items, capacity);
        printf("%d", knapsack->dynamicProgramming());
        return 0;
    }
    
    

    输入数据

    5 9
    2 10
    4 11
    6 12
    8 13
    9 14
    

    输出结果

    22
    

    鸣谢

    《算法竞赛入门经典》

    最后

    • 由于博主水平有限,不免有疏漏之处,欢迎读者随时批评指正,以免造成不必要的误解!
    展开全文
  • 连续子数组最大和 输入一个整型数组数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。...​ 大致思路:定义一个和目标数组num一样大小的动态规划数组dp,遍历后d

    连续子数组最大和

    输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

    要求时间复杂度为O(n)。

    示例1:

    输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

    提示:

    1 <= arr.length <= 10^5
    -100 <= arr[i] <= 100

    动态规划解析:

    ​ 大致思路:定义一个和目标数组num一样大小的动态规划数组dp,遍历后dp[i]的值为以元素num[i]为结尾的连续子数组最大和,实现的原理如下

    状态定义:

    1.设动态规划列表dp , dp[i] 代表以元素nums[i]为结尾的连续子数组最大和

    ​ 为何定义最大和dp[i]中必须包含元素nums[i] :保证dp[i]递推到dp[i + 1]的正确性;

    ​ 如果不包含nums[i] ,递推时则不满足题目的连续子数组要求。

    2.转移方程:若dp[i-1]≤0,说明dp[i- 1]对dp[i]产生负贡献,即dp[i - 1] + nums[i]还不如nums[i]本身大。

    ​ 当dp[i-1]> 0时:执行dp[i] = dp[i- 1] + nums[i] ;

    ​ 当dp[i -1]≤0时:执行dp[i]= nums[i];

    3.初始状态:

    ​ dp[0] = nums[0],即以nums[0]结尾的连续子数组最大和为nums[0]。

    4.返回值:

    ​ 返回dp列表中的最大值,代表全局最大值。

    在这里插入图片描述

    public int maxSubArray1(int[] nums){//暴力破解2优化,O(n^2)
            int n = -100;
            for (int i = 1; i < nums.length; i++) {
                int sum = 0;
                for (int j = i; j <= nums.length; j++){
                    sum += nums[j];
                    if (sum > n){
                        n = sum;
                    }
                }
            }
            return n;
        }
    public int maxSubArray2(int[] nums){//动态规划
            
            //创建一个同样大小的数组dp[i]表示以元素num[i]为结尾的连续子数组最大和
            int[] dp = new int[nums.length];
            dp[0]=nums[0];//初始化dp[0]
            for(int j = 1;j<nums.length;j++){
                //判断条件,dp[j-1]>0表示以元素num[i]为结尾的连续子数组最大和大于0
                // 即可对之后组成更大的连续子数组有正贡献
                //dp[j-1]<0,表示以元素num[i]为结尾的连续子数组最大和小于0,
                // 不再参与之后的连续子数组,子数组从新积累
                if(dp[j-1]>0){
                    dp[j] = dp[j-1]+nums[j];
                }else{
                    dp[j] = nums[j];
                }
            }
            int max = Integer.MIN_VALUE;
            for(int i = 0;i<dp.length;i++){//遍历dp,找到最大值
                if(dp[i]>max)
                    max = dp[i];
            }
            return max;
        }
    
    public int maxSubArray3(int[] nums) {//同样的功能大佬的代码简单到离谱,阿巴阿巴
            int res = nums[0];
            for(int i = 1; i < nums.length; i++) {
                nums[i] += Math.max(nums[i - 1], 0);
                res = Math.max(res, nums[i]);
            }
            return res;
        }
    
    public class MaxSubArray {
        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};//结果为6,ok
            System.out.println(solution.maxSubArray3(arr));
        }
    }
    

    总结:动态规划入门,这道题开始连最简单的暴力破解都没独立写出来,现在对这些解题思路豁然开朗,太厉害了。

    暴力破解是双重循环比较每个子数组和的大小,从0开始[0],[0,1],[0,1,2],一直到[0,1,2,…n],然后再从1开始,[1],[1,2],[1,2,3]一直到[1,2,…n],然后再从2开始…

    sum(0,0)
    sum(0,1) sum(1,1)
    sum(0,2) sum(1,2) sum(2,2)
    sum(0,3) sum(1,3) sum(2,3)

    --------------------------------------->

    而此题的动态规划思路是先找到每个以num[i]结尾的数组的最大子数组和存入数组dp,再遍历dp找到最大值

    最大值
    sum(0,0) dp[0]
    sum(0,1) sum(1,1) dp[1]
    sum(0,2) sum(1,2) sum(2,2) dp[2]
    sum(0,3) sum(1,3) sum(2,3) dp[3]
    dp[j]

    最大值dp[j]的计算方法

    dp[j] = dp[j-1]+nums[j]; dp[j-1]>0

    dp[j] = nums[j]; dp[j-1]<0

    自己用例子计算一遍给出的例子就能够理解这个方法

    展开全文
  • 虽然接触动态规划算法已经有一段时间,给一个01背包问题,能够做到一个表格简单粗暴下去,然后求得结果,但心里总觉得对这个算法理解十分不到位,抱着对算法的热爱,网上很多大牛的算法思维实在让我佩服的五体投地。...

      虽然接触动态规划算法已经有一段时间,给一个01背包问题,能够做到一个表格简单粗暴下去,然后求得结果,但心里总觉得对这个算法理解十分不到位,抱着对算法的热爱,网上很多大牛的算法思维实在让我佩服的五体投地。在此讲一讲动态规划中滚动数组的求解方法,算是对这个知识点做一个记录,也希望有写的不妥的地方,大家能不吝赐教。

      首先,我们先看看“滚动数组”的例题,大家可以参考http://www.lintcode.com/en/problem/house-robber/

      题意大概就是说:一个盗贼要去偷盗一系列房子的财物,房子之间有报警器,当且仅当两个相邻的房子同时被偷盗的时候会自动报警,每个房子有一定的价值量,请问盗贼怎么做才能偷到最大价值的量。

      求解这类题目要注意以下四点要素(也可以说是动态规划题目的四点要素):

      1、状态(State)

        用于存储小规模问题的结果

      2、方程(Function)

        由状态推出的一个方程,即怎么通过小的状态来推出大的状态

      3、初始化(Initialization)

        最初的状态,作为方程的起点

      4、结果(Result)

        根据每步的状态求出的结果

      回到House-Robber这个题目,这个题目是个典型的滚动数组类型题。给定一个数组,我们不能够取相邻的两个元素,怎么取法可以使取得的结果和最大。比如给定[4,9,1],我们可以取[4,1]或者取[9],很明显一个结果是5,一个结果是9,所以我们这里的结果应该是后者的取法。在状态的确立上,我们可以这么理解,用A[n]数组表示每个元素(下标从0开始),当我们遇到第 i 个元素的时候,我们是取不取,当我们取了第i-1个元素的时候,我们就不能取了,要不就去掉第i-1个元素,以便于取得第i个元素。如果我们用f[n]来代表当遇到第n个元素,我们做出行动(取还是不取)之后,能够获得的最大值,那当取到第i个元素的时候,我们就是判断f[i-2] + A[i]和f[i-1]的大小,然后f[i] = max(f[i-2]+A[i],f[i-1]),你说是不是呢?我们无须去管i-3之前的元素是怎么取的,因为按照这个规律来,在f[i-2]已经包含了到i-2个元素位置能够取得的最大量了。

      至此,以上已经阐明了这个思路的【状态】还有【方程】,剩下【初始化状态】和【结果】,我们可以注意到确定第i个方程的结果,往前需要用到i-2的元素,所以第0个元素和第1一个元素需要作为初始化的内容,因为这两个元素均不能用i-2的元素推倒出来,所以有f[0] = A[0],f[1] = max(A[1],A[0])。而结果就是我们对第n-1个元素做出行动之后的结果,该结果存储在f[n-1]当中。

    通过代码实现:

    long long houseRobber(vector<int> A){
            if(0 == A.size()) return 0;
            int f[A.size()];
            f[0] = A[0];
            if(A.size()>1) f[1] = max(A[0],A[1]);
            for(int i =2;i<A.size();i++)
                f[i] = A[i] + f[i-2]> f[i-1]? A[i] +f[i-2]:f[i-1];
            return f[A.size()-1];
        }

    这样,在时间复杂度O(n)可以求得结果,空间复杂度为O(n)。

    【在这里我稍微拓展一下,f[i]的结果是通过对比f[i-2]+A[i]和f[i-1]的结果得来的,那其实i-3及其以前的空间都不需要再用到,所以我们可以只用三个空间重复使用来表示每一个状态,以达到空间复杂度为O(1)】

    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

      以上就是对一位数组的滚动数组算法求解过程,接下来探讨一下二维数组的滚动数组求解过程,大家可以参考http://www.lintcode.com/en/problem/maximal-square/

      题意:给定一个只包含01的二维数组,求出最大的正方形,使这个正方形的所有元素都为1

      我们用Matrix[n][m]表示这个二维数组,dp[n][m]表示左上角最大符合条件的正方形边长。首先,四个要素我们先来确定一下。【状态】我们要确定第[i,j]的状态要怎么确定呢,往前推一步有三个状态,分别是[i-1,j],[i,j-1]和[i-1,j-1],这三个状态同样表示了左上角最大的正方形,我们通过图来表示理解一下:

                      

      这里为了方便画出了dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相等的情况,可以很容易看出,当dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相等的时候dp[i][j]等于dp[i-1][j],dp[i][j-1],dp[i-1][j-1]其中的一个加上1,如果dp[i-1][j],dp[i][j-1],dp[i-1][j-1]不相等,那dp[i][j]取决于dp[i-1][j],dp[i][j-1],dp[i-1][j-1]之中小的那一个,这里偷懒就不画图了,大家可以自己动手画画看,嘿嘿~。因此【状态】确定了,【方程】也就容易得到dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。【初始化状态】可以想到从[1,1]开始才能应用这个方程(假定我们是从[0,0]向[n,m]逐渐确定状态),所以i=0和j=0都是需要初始化的内容,这种情况下dp[i][j] = Matrix[i][j]。【结果】为dp矩阵中最大值的平方max{dp[n][m]}2

    代码实现:

    int maxSquare(vector<vector<int> > &matrix) {
            // write your code here
            int row = matrix.size();
            int col = matrix[0].size();
            int dp[row][col];
            int _max = 0;
            for(int i =0;i<row;i++){
                dp[i][0] = matrix[i][0];
                dp[i][col-1] = matrix[i][col-1];
                _max = dp[i][0]|dp[i][col-1];
            }
            for(int i =0;i<col;i++){
                dp[0][i] = matrix[0][i];
                dp[row-1][i] = matrix[row-1][i];
                _max = dp[0][i]|dp[row-1][i];
            }
            for(int i =1;i<row;i++)
                for(int j = 1;j<col;j++){
                    if(1 == matrix[i][j]) dp[i][j] = min3(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) +1;
                    else dp[i][j] = matrix[i][j];
                    _max = max(dp[i][j],_max);
    
                }
            return _max*_max;
        }

    时间复杂度为O(n*m),空间复杂度为O(n*m)

    【拓展:参考一位数组的拓展思路,我们确定[i,j]个状态,分别用到[i-1,j],[i,j-1],[i-1,j-1]这三个状态,所以我们可以想到可以用4个空间来重复表示各个状态,但由于对于二维数组,当换行的时候到了行首会丢失这个状态(因为4个空间在表示上一行末尾的四个状态了),所以我们只能用两行(2*n)个空间来维持这个状态】下面给出拓展后的代码,大家仅供参考,因为初始化状态被写在遍历过程中,可能会造成混乱,请谅解:

    int maxSquare(vector<vector<int> > &matrix) {
            int row = matrix.size();
            int col = matrix[0].size();
            int dp[2][col];
            int _max = 0;
            for(int i =0;i<col;i++) dp[0][i] = matrix[0][i];
            for(int i =1;i<row;i++)
                for(int j=0;j<col;j++){
                    if( 0 == j ) dp[1][j] = matrix[i][j];
                    else{
                        if(1 == matrix[i][j]) dp[1][j] = min3(dp[0][j],dp[1][j-1],dp[0][j-1])+1;
                        else dp[1][j] = 0;
                    }
                    _max = max(_max,dp[1][j]);
                    dp[0][j-1] = dp[1][j-1];
                }
                dp[0][col-1] = dp[1][col-1];
            return _max*_max;
        }

    这样空间复杂度可以降到O(m)。

    以上为个人对滚动数组的求解过程的理解,每一句代码均经过本人测试可用,如有问题,希望大家提出斧正。

     

     

     

    尊重知识产权,转载引用请通知作者并注明出处!

    转载于:https://www.cnblogs.com/GNLin0820/p/6434693.html

    展开全文
  • 动态规划是解决多决策问题的一种解决方案,而非一种算法。其中心思想在于,将原问题分解成多个子问题,通过子问题的求解,得到原问题的答案。 01背包问题: 题目描述:有编号a,b,c,d,e的物件物品,他们的重量分别是2...

    动态规划是解决多决策问题的一种解决方案,而非一种算法。其中心思想在于,将原问题分解成多个子问题,通过子问题的求解,得到原问题的答案。


    01背包问题:

    题目描述:有编号a,b,c,d,e的物件物品,他们的重量分别是2,2,6,5,4.他们的价值分别是6,3,5,4,6现在给到承重10的背包,如何将背包装入的物品具有最大价值总和.


    表格从上到下,从左向右,c4表示当背包承重为4时,有物品a,b,c可装入时,背包最大价值。


    背包转换方程::f[i,j]=Max{f[i-1,j-Wi]+Pi(j>=Wi),f[i-1,j]}

    f[i,j] 表示在前i件物品中,选择若干件放在背包承重j的背包中以获得最大价值。

    Pi 物品i的价值.

    Wi物品i的重量

    问题决策:为了使背包承重j的价值最大,物品i是否需要放进背包。

    附代码:

    #include "stdafx.h"

    int max(int a,int b)
    {
    	return a>b?a:b;
    }
    /*
    0 1 背包
    */
    int MaxValue()
    {
        int Weight[5]={2,2,6,5,4};//物品的重量数组    
        int Value[5]={6,3,5,4,6};//物品价值数组
        int Total_Count = 5/*物品个数*/,
    	Total_w = 10 /*背包承重*/;
    	int f[5][10]={0};
    	
    	for(int Cur_w =1;Cur_w <= Total_w;Cur_w++)//背包重量
        {
    		for(int i=0;i<Total_Count;i++)//物品个数
            {    
                {
    				//这里需要考虑Cur_w是否大于Weight
    				if(Cur_w >= Weight[i])
    				{
    					if(i==0)//第一件物品
    					{
    						f[i][Cur_w-1] = Value[i];
    					}
    					else
    					{
    						f[i][Cur_w-1] = max(f[i-1][Cur_w-1-Weight[i]]+Value[i],f[i-1][Cur_w-1]);	
    					}
    				}
    				else//当前背包承重小于i物品的重量时
    				{
    					//同样考虑第一件物品的情况
    					if(i==0)
    					{
    						f[i][Cur_w-1] = 0;	
    					}
    					else
    					{
    						f[i][Cur_w-1] = f[i-1][Cur_w-1];	
    					}								
    				}
                } 
             }
        }
    	return f[4][9];
    }
    
    
    
    最大子数组和。
    问题描述:一个整数数组,一个非空的字数组,求它的最大和
    设定dp[i]表示以a[i]结尾的最大字数组和
    问题转化:dp[i] = max(dp[i-1]+a[i],a[i]) 
    dp[i]取决于dp[i-1]+a[i]和a[i]的最大值。
    代码:
    
    /*
    最大子数组
    */
    #include<vector>
    using namespace std;
    int MaxSubarray(int a[],int n)
    {
    	vector<int> dp(n);
    	dp[0] = a[0];
    	int maxSub =a[0];
    	for(int i=1;i<n;i++)
    	{
    		dp[i] = max(dp[i-1]+a[i],a[i]);
    		maxSub = max(dp[i],maxSub);//记录每一次的字数组和,并取到最大值
    	}
    	return maxSub;
    }
    
    
    
    最小路径: min(A->E)=min((A->B1)+min(B1->E),(A->B2)+min(B2->E))
    同样,将A->E的最小路径问题转化为B1->E,B2->E的子问题,求出子问题后,再求解原始问题。
    如下二维矩阵,表示从列A->E 到 行A->E的所有路径,除过有直接到E的几个节点外
    其他均为0,优化期间path[i][10]表示经计算后i点到E的最小路径。所以
    path[i][10]=min(path[i][j]+path[j][10],path[i][j+1]+path[j+1][10],...);
    path[i][j]表示i行所有不为0的项。
    
    /*
    最短路径
    */
    int path[11][11] =
    //终点	A	B1	B2	C1	C2	C3	C4	D1	D2	D3	E
    /*起点*/
    /*A*/{  0,	5,	3,	0, 	0,	0,	0,	0,	0,	0,	0,
    /*B1*/	0,	0,	0,	1,	6,	3,	0,	0,	0,	0,	0,
    /*B2*/	0,	0,	0,	0,	0,	8,	4,	0,	0,	0,	0,
    /*C1*/	0,	0,	0,	0,	0,	0,	0,	5,	6,	0,	0,
    /*C2*/	0,	0,	0,	0,	0,	0,	0,	5,	0,	0,	0,
    /*C3*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	8,	0,
    /*C4*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	3,	0,
    /*D1*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	3,
    /*D2*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	4,
    /*D3*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	3,
    /*E*/	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0};
    
    int MinPath()
    {
    	int i,j;
    	for(i=9;i>=0;i--)
    	{
    		vector<int> temp(11);
    		for(j=10;j>=0;j--)
    		{
    		//用当前行中,除最后一列的所有数字,加上path[j][10],取最小 ,赋给path[i][11];		
    			if(path[i][j] > 0 && j!=10)//此处需要判断边界条件
    			{
    				temp[j] = path[j][10]+path[i][j];				
    			}
    		}
    		vector<int>::iterator it =temp.begin();
    		int temp_minipath = 10000;//指定一个远大于所有路径之和的所有值
    		for(;it!=temp.end();it++)
    		{
    			if(*it!=0)
    			{
    				temp_minipath = temp_minipath < *it?temp_minipath:*it;
    			}		
    		}
    		if(temp_minipath != 10000)
    			path[i][10] = temp_minipath;//求当前点到E的最小路径	
    	}
    	return path[0][10];
    }
    
    
    /*
    斐波那契数列
    */
    斐波那契数列:动态规划的优化在于将所有计算过的选项用数组dp[n]保存起来,下次计算的时候,直接
    运用,跳过指数级的重复计算过程。
    int DpFiboArray(int n)
    {
    	static vector<int> dp(n+1);
    	if(n==0 || n==1)
    	{
    		dp[n] = 1;
    		return dp[n];
    	}
    	else
    	{
    		if(dp[n-1] == 0)
    			dp[n-1] = DpFiboArray(n-1);	
    		if(dp[n-2] == 0)
    			dp[n-2] = DpFiboArray(n-2);
    		dp[n] = dp[n-1]+dp[n-2];
    	}
    	return dp[n];
    }
    
    int FiboArray(int n)
    {
    	if(n==0 || n==1)
    		return 1;
    	else
    		return FiboArray(n-1)+FiboArray(n-2);
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	// 01背包
    	int result = MaxValue();
    
    	//最大字数组
    	int a[10]={31,-41,59,26,-53,58,97,-93,-23,84};
    	int maxsub =MaxSubarray(a,10);
    
    	//最短路径
    	int minpath = MinPath();
    
    	//斐波那契数列
    	int FiboNum =DpFiboArray(20); 
    
    	return 0;
    }
    


    展开全文
  • 题意: 往手镯上镶嵌宝石,手镯总重量有上限,... 动态规划问题主要是找到子问题,即一旦确定了第i个状态,就可以直接推出第i+1个状态。(有后效性)以题目给出的数据举例: 4 6 n m ① 1 4 w[i] v[i] ② 2 6 ③ ...
  • 一开始学完01背包的二维写法,再看一维写法是一脸懵逼的,自己推导了几遍过程,终于是理解了!!!分享一下蒟蒻的心得,背包问题可以去看一下胡凡的算法笔记。 问题如下:有n个重量和价值分别为wi,vi的物品。从这些...
  • 这道题就是用二维数组解决的时候,就是简单的动态规划,但是坑就坑在可能出现体积为0但是价值不为0的例子   一:二维数组 下面是错误的代码 #include &lt;iostream&gt; #include &lt;cstring&...
  • 由经典的 01背包问题 入手 已知:背包最大容积pack_max ,物品总数thing_max(每件物品的体积tiji ,价值val) 求解:背包可装入物品的总的最大价值是多少 思路: 子问题:第i体积状态(小于或等于)下最大价值=第i -1体积...
  • 动态规划空间优化之滚动数组

    千次阅读 2019-08-06 20:30:15
    动态规划本就是一个记录再利用的高效算法,由于其要记录之前的状态,必然会使用大量空间,要优化动态规划算法的空间,我们必然要合理利用dp数组,有一种优化方法就是利用滚动数组来进行状态转移。 我们拿动态规划中...
  • 动态规划是将大问题分解成许多小问题,通过寻找大问题与小问 题之间的递推关系,解决一个一个小问题,最终达到解决原问题 的目的。通过填表将每个子问题的解记录下来,在新问题里需要 用到时可以直接提取,节约...
  • 题目描述 有N件物品,第i件物品的重量是W[i],它的价值是V[i],每件...遇到动态规划问题写不出来的话就写暴力递归 int maxPrix(vector<int>& W, vector<int>& V, int C, int i) { if (i == W....
  • 01背包问题(动态规划) 题目描述: 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大...
  • 这题还算是一道比较基础的动态规划问题啦, 和01背包问题略有类似, 都需要考虑容量和复杂度优化, 之前定义状态总想着能二维就二维, 现在看来很多时候其实可以直接用一维的思路去定义状态, 反而会简便很多 定义dp[i] ...
  • 起到优化空间,主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底向上的扩展过程,我们常常需要用到的是连续的解,前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大...
  • 题目大意:过生日,有一个N*M的表格,每个位置...题目思路:之前的01背包我们都是用一维数组v[i]来储存的,但这次要用二维数组Map[i][j]储存一个点的价值,当前点由Map[i][j-1]或Map[i-1][j]走到。 #include<iost...
  • 参考链接:面试题:把数组中的数分为两组,使得两组和相差最小 timus 1005. Stone Pilehttps://blog.csdn.net/pegasuswang_/article/details/25081783 这个转换成01背包是我没想到的! 不得不说这个思路是怎么想到...
  • ...n,j:c...0的顺序,(按照这种顺序推算,也许就可以发现后面讲的优化为一维数组的方法。) 74 75 路径记录 76 之前不是说每一件物品都有放或不放两种选择吗,想要记录路径就得在放的时候给标记一下。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 610
精华内容 244
关键字:

动态规划01数组