精华内容
下载资源
问答
  • 动态规划求解01背包问题

    千次阅读 2019-04-22 21:35:05
    动态规划和分治法有些相像,都是把一个问题分成了很多子问题求解,但是不同的是动态规划会记忆之前解决的子问题的结果,避免了重复计算。判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后...

    近期事情多,且老师讲动态规划讲得云里雾里。。于是又没有跟上进度,菜鸡终于要来填坑了。

    动态规划

    动态规划和分治法有些相像,都是把一个问题分成了很多子问题来求解,但是不同的是动态规划会记忆之前解决的子问题的结果,避免了重复计算。判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后写出递推关系式。

    动态规划得到的解一定是最优解。

    01背包问题
    (1)问题描述:
    现有n件物品,每件都有对应的重量(w)和价值(v),有一个给定容量(C)的背包,怎么样才能在背包里装入具有最大价值总和的东西?
    具体例子:
    在这里插入图片描述
    (2)问题分析:
    突然想到之前看数模书的时候提到的一种思路——引入0-1变量,化为整数规划问题。
    模型建立:已知n件物品的重量为W1~Wn ,价值为V1 ~Vn,用X1 ~Xn来表示是否选了这件物品放入背包,Xi为0或1。
    决策目标即为:MAX(V1X1+V2X2+…+VnXn)
    约束条件即为:(W1X1+W2X2+…+WnXn) ≦ C
    抖机灵用lingo求了下解。。
    在这里插入图片描述
    好了言归正传。。
    (3)寻找子问题和建立递推关系式
    这里采用自底向上的思路
    定义子问题:在前i个物品里面挑选总重量不大于W(W<=C)的物品,记最优值为M(i, W),则对于第i个物品来说就有两种情况:
    ①Wi>W,装不下了,则M(i, W)=M(i-1, W);
    ②Wi<=W,那么就要选择装不装,则M(i, W)=max{M(i-1, W) , M(i-1, W-Wi)+Vi}
    M(i-1, W-Wi)即为第i个物品装入之前的最优值,结果是装了第i个物品。
    接下来就是初始化的问题了,还是看源代码吧。
    (4)源代码:

    public class FindMax {	
    	public static void main(String[] args){
    		int capacity=11;
    		int item_num=5;
    		int[][] M = new int[item_num+1][capacity+1];
    		int[] w={0,1,2,5,6,7};
    		int[] v={0,1,6,18,22,28};
    		int i,j;
    		for(i=0;i<=capacity;i++){
    			M[0][i]=0;
    		}
    		for(j=0;j<=item_num;j++){
    			M[j][0]=0;
    		}
    		for(i=1;i<=item_num;i++){
    			for(j=1;j<=capacity;j++){
    				if(w[i]>j){
    					M[i][j]=M[i-1][j];
    				}
    				else{
    					M[i][j]=Math.max(M[i-1][j], M[i-1][j-w[i]]+v[i]);
    				}
    			}
    		}
    		for(i=0;i<=item_num;i++){
    			for(j=0;j<=capacity;j++){
    				System.out.print(M[i][j]+ "\t");
    			}
    			System.out.println("");
    		}
    	}
    }
    

    结果截图如下:
    在这里插入图片描述
    最优解为40,那么怎么知道是哪几件物品被选中了呢?我们要从表的右下角往回看,M(5, 11)=M(4, 11)=40且M(4,11)不等于M[3,11],说明选了4号物品;减去4号物品的重量40-22=18,M(3, 5)=18且M(3,5)不等于M(2, 5)且M(3,5)=M(4,5)=M(5,5),说明第三件物品被选择了,减去三号物品的重量40-22-18=0;说明被选中的就是3号和4号。

    今天就写到这里吧。

    展开全文
  • 使用动态规划求解01背包问题的程序,使用C语言编写。
  • 主要介绍了Python基于动态规划算法解决01背包问题,结合实例形式分析了Python动态规划算法解决01背包问题的原理与具体实现技巧,需要的朋友可以参考下
  • 对一个实际的背包问题,分别采用动态规划法和回溯法,以动态图ppt的形式生动形象地展示这两种算法的原理和求解过程
  • 问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i...

    问题描述

    有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

    为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8

    i(物品编号)1234
    w(体积)2345
    v(价值)3456

     

    总体思路

    根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。

    动态规划的原理

    动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。

    最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。

    背包问题的解决过程

    在解决问题之前,为描述方便,首先定义一些变量:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值,同时背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选)。

    1、建立模型,即求max(V1X1+V2X2+…+VnXn);

    2、寻找约束条件,W1X1+W2X2+…+WnXn<capacity;

    3、寻找递推关系式,面对当前商品有两种可能性:

    • 包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);
    • 还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}。

    其中V(i-1,j)表示不装,V(i-1,j-w(i))+v(i) 表示装了第i个商品,背包容量减少w(i),但价值增加了v(i);

    由此可以得出递推关系式:

    • j<w(i)      V(i,j)=V(i-1,j)
    • j>=w(i)     V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}

    这里需要解释一下,为什么能装的情况下,需要这样求解(这才是本问题的关键所在!):

    可以这么理解,如果要到达V(i,j)这一个状态有几种方式?

    肯定是两种,第一种是第i件商品没有装进去,第二种是第i件商品装进去了。没有装进去很好理解,就是V(i-1,j);装进去了怎么理解呢?如果装进去第i件商品,那么装入之前是什么状态,肯定是V(i-1,j-w(i))。由于最优性原理(上文讲到),V(i-1,j-w(i))就是前面决策造成的一种状态,后面的决策就要构成最优策略。两种情况进行比较,得出最优。

    4、填表,首先初始化边界条件,V(0,j)=V(i,0)=0;

    然后一行一行的填表:

    • 如,i=1,j=1,w(1)=2,v(1)=3,有j<w(1),故V(1,1)=V(1-1,1)=0;
    • 又如i=1,j=2,w(1)=2,v(1)=3,有j=w(1),故V(1,2)=max{ V(1-1,2),V(1-1,2-w(1))+v(1) }=max{0,0+3}=3;
    • 如此下去,填到最后一个,i=4,j=8,w(4)=5,v(4)=6,有j>w(4),故V(4,8)=max{ V(4-1,8),V(4-1,8-w(4))+v(4) }=max{9,4+6}=10……

    所以填完表如下图:

    5、表格填完,最优解即是V(number,capacity)=V(4,8)=10。

     

    代码实现

    为了和之前的动态规划图可以进行对比,尽管只有4个商品,但是我们创建的数组元素由5个。

    #include<iostream>
    using namespace std;
    #include <algorithm>
    
    int main()
    {
    	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
    	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
    	int bagV = 8;					        //背包大小
    	int dp[5][9] = { { 0 } };			        //动态规划表
    
    	for (int i = 1; i <= 4; i++) {
    		for (int j = 1; j <= bagV; j++) {
    			if (j < w[i])
    				dp[i][j] = dp[i - 1][j];
    			else
    				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    		}
    	}
    
    	//动态规划表的输出
    	for (int i = 0; i < 5; i++) {
    		for (int j = 0; j < 9; j++) {
    			cout << dp[i][j] << ' ';
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

     

    背包问题最优解回溯

    通过上面的方法可以求出背包问题的最优解,但还不知道这个最优解由哪些商品组成,故要根据最优解回溯找出解的组成,根据填表的原理可以有如下的寻解方式:

    • V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
    • V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
    • 一直遍历到i=0结束为止,所有解的组成都会找到。

    就拿上面的例子来说吧:

    • 最优解为V(4,8)=10,而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10,所以第4件商品被选中,并且回到V(3,8-w(4))=V(3,3);
    • 有V(3,3)=V(2,3)=4,所以第3件商品没被选择,回到V(2,3);
    • 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4,所以第2件商品被选中,并且回到V(1,3-w(2))=V(1,0);
    • 有V(1,0)=V(0,0)=0,所以第1件商品没被选择。

     

    代码实现

    背包问题最终版详细代码实现如下:

    #include<iostream>
    using namespace std;
    #include <algorithm>
    
    int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
    int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
    int bagV = 8;					        //背包大小
    int dp[5][9] = { { 0 } };			        //动态规划表
    int item[5];					        //最优解情况
    
    void findMax() {					//动态规划
    	for (int i = 1; i <= 4; i++) {
    		for (int j = 1; j <= bagV; j++) {
    			if (j < w[i])
    				dp[i][j] = dp[i - 1][j];
    			else
    				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    		}
    	}
    }
    
    void findWhat(int i, int j) {				//最优解情况
    	if (i >= 0) {
    		if (dp[i][j] == dp[i - 1][j]) {
    			item[i] = 0;
    			findWhat(i - 1, j);
    		}
    		else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
    			item[i] = 1;
    			findWhat(i - 1, j - w[i]);
    		}
    	}
    }
    
    void print() {
    	for (int i = 0; i < 5; i++) {			//动态规划表输出
    		for (int j = 0; j < 9; j++) {
    			cout << dp[i][j] << ' ';
    		}
    		cout << endl;
    	}
    	cout << endl;
    
    	for (int i = 0; i < 5; i++)			//最优解输出
    		cout << item[i] << ' ';
    	cout << endl;
    }
    
    int main()
    {
    	findMax();
    	findWhat(4, 8);
    	print();
    
    	return 0;
    }

     

    展开全文
  • 动态规划求解01背包问题C++代码

    千次阅读 2020-05-20 10:39:07
    动态规划求解01背包问题 以下代码为动态规划求解01背包问题并统计代码运行300遍的平均运行时间。 #include <iostream> #include <windows.h> #include <iomanip> #include <time.h> ...

    动态规划法求解01背包问题

    以下代码为动态规划法求解01背包问题并统计代码运行300遍的平均运行时间

    #include <iostream>
    #include <windows.h>
    #include <iomanip>
    #include <time.h>
    
    using namespace std;
    
    int KnapSack(int w[], int v[], int n, int C){
        int V[n+1][C+1];
        int i, j;
        int x[n+1];
        for(i=0; i<=n; i++) //a[0] 到 a[n]
            V[i][0] = 0;    //初始化第0列
        for(j=0; j<=C; j++)
            V[0][j] = 0;    //初始化第0行
    
        for(i=1; i<=n; i++)
            for(j=1; j<=C; j++)
                if(j<w[i])
                    V[i][j] = V[i-1][j];
                else
                    V[i][j] = max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
        for(j=C,i=n; i>0; i--){
            if(V[i][j]>V[i-1][j]){
                x[i]=1;
                j=j-w[i];
            }
            else
                x[i]=0;
        }
        return V[n][C];
    }
    
    int main()
    {
    
    
        LARGE_INTEGER nFreq;
        LARGE_INTEGER nBeginTime;
        LARGE_INTEGER nEndTime;
        double time;
    
        int w[] = {0,2,2,6,5,4};
        int v[] = {0,6,3,5,4,6};
        int n=5, C = 10;	//5个物品,背包最大重量为10
        int m;
    
        int i=0;
        double SumTime=0.0;
        QueryPerformanceFrequency(&nFreq);
        while(i<300){
            QueryPerformanceCounter(&nBeginTime);
    
            m = KnapSack(w,v,n,C);
    
            QueryPerformanceCounter(&nEndTime);
            time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)*1000000000/(double)(nFreq.QuadPart);
            SumTime+=time;
            i++;
        }
        time = SumTime/300.0;
        cout << "Max Value is " << m << endl;
        cout << "Average running time is : "  << time << " ns."; //单位是纳秒.
        return 0;
    }
    
    
    展开全文
  • 动态规划解决01背包问题

    千次阅读 2019-03-08 19:55:54
    一、问题描述:有n 个物品,它们有各自的重量和...二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出0...

    转自:https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

    一、问题描述:有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

    二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现;

    三、动态规划的原理及过程:

      eg:number=4,capacity=8

    i

    1

    2

    3

    4

    w(体积)

    2

    3

    4

    5

    v(价值)

    3

    4

    5

    6

     

    1原理

      动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。

    2过程

      a) 把背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选),Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积(重量);

      b) 建立模型,即求max(V1X1+V2X2+…+VnXn);

      c) 约束条件,W1X1+W2X2+…+WnXn<capacity;

      d) 定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值;

      e) 最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理,采用反证法证明:

        假设(X1,X2,…,Xn)是01背包问题的最优解,则有(X2,X3,…,Xn)是其子问题的最优解,

        假设(Y2,Y3,…,Yn)是上述问题的子问题最优解,则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1;

        而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn),则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn);

        该式子说明(X1,Y2,Y3,…,Yn)才是该01背包问题的最优解,这与最开始的假设(X1,X2,…,Xn)是01背包问题的最优解相矛盾,故01背包问题满足最优性原理;

      f) 寻找递推关系式,面对当前商品有两种可能性:

        第一,包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);

        第二,还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{ V(i-1,j),V(i-1,j-w(i))+v(i) }

           其中V(i-1,j)表示不装,V(i-1,j-w(i))+v(i) 表示装了第i个商品,背包容量减少w(i)但价值增加了v(i);

        由此可以得出递推关系式:

        1) j<w(i)      V(i,j)=V(i-1,j)

        2) j>=w(i)     V(i,j)=max{ V(i-1,j)V(i-1,j-w(i))+v(i) 

      g) 填表,首先初始化边界条件,V(0,j)=V(i,0)=0;

     

      h) 然后一行一行的填表,

        1) 如,i=1,j=1,w(1)=2,v(1)=3,有j<w(1),故V(1,1)=V(1-1,1)=0;

        2) 又如i=1,j=2,w(1)=2,v(1)=3,有j=w(1),故V(1,2)=max{ V(1-1,2),V(1-1,2-w(1))+v(1) }=max{0,0+3}=3;

        3) 如此下去,填到最后一个,i=4,j=8,w(4)=5,v(4)=6,有j>w(4),故V(4,8)=max{ V(4-1,8),V(4-1,8-w(4))+v(4) }=max{9,4+6}=10;所以填完表如下图:

     

    复制代码

     1 void FindMax()//动态规划
     2 {
     3     int i,j;
     4     //填表
     5     for(i=1;i<=number;i++)
     6     {
     7         for(j=1;j<=capacity;j++)
     8         {
     9             if(j<w[i])//包装不进
    10             {
    11                 V[i][j]=V[i-1][j];
    12             }
    13             else//能装
    14             {
    15                 if(V[i-1][j]>V[i-1][j-w[i]]+v[i])//不装价值大
    16                 {
    17                     V[i][j]=V[i-1][j];
    18                 }
    19                 else//前i-1个物品的最优解与第i个物品的价值之和更大
    20                 {
    21                     V[i][j]=V[i-1][j-w[i]]+v[i];
    22                 }
    23             }
    24         }
    25     }
    26 }

    复制代码

      i) 表格填完,最优解即是V(number,capacity)=V(4,8)=10,但还不知道解由哪些商品组成,故要根据最优解回溯找出解的组成,根据填表的原理可以有如下的寻解方式:

        1) V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);

        2) V(i,j)=V(i-1,j-w(i))+v(i)实时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));

        3) 一直遍历到i=0结束为止,所有解的组成都会找到。

      j) 如上例子,

        1) 最优解为V(4,8)=10,而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10,所以第4件商品被选中,并且回到V(3,8-w(4))=V(3,3);

        2) 有V(3,3)=V(2,3)=4,所以第3件商品没被选择,回到V(2,3);

        3) 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4,所以第2件商品被选中,并且回到V(1,3-w(2))=V(1,0);

        4) 有V(1,0)=V(0,0)=0,所以第1件商品没被选择;

     

      k) 到此,01背包问题已经解决,利用动态规划解决此问题的效率即是填写此张表的效率,所以动态规划的时间效率为O(number*capacity)=O(n*c),由于用到二维数组存储子问题的解,所以动态规划的空间效率为O(n*c);

    复制代码

     1 void FindWhat(int i,int j)//寻找解的组成方式
     2 {
     3     if(i>=0)
     4     {
     5         if(V[i][j]==V[i-1][j])//相等说明没装
     6         {
     7             item[i]=0;//全局变量,标记未被选中
     8             FindWhat(i-1,j);
     9         }
    10         else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
    11         {
    12             item[i]=1;//标记已被选中
    13             FindWhat(i-1,j-w[i]);//回到装包之前的位置
    14         }
    15     }
    16 }

    复制代码

    3、空间优化

      l) 空间优化,每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关,V(i-1)(x)是前一次i循环保存下来的值;

      因此,可以将V缩减成一维数组,从而达到优化空间的目的,状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}

      并且,状态转移方程,每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的,所以一维数组中j的扫描顺序应该从大到小(capacity到0),否者前一次循环保存下来的值将会被修改,从而造成错误。

     

      m) 同样以上述例子中i=3时来说明,有:

        1) i=3,j=8,w(3)=4,v(3)=5,有j>w(3),则B(8)=max{B(8),B(8-w(3))+v(3)}=max{B(8),B(4)+5}=max{7,4+5}=9;

        2) j- -即j=7,有j>w(3),则B(7)=max{B(7),B(7-w(3))+v(3)}=max{B(7),B(3)+5}=max{7,4+5}=9;

        3) j- -即j=6,有j>w(3),则B(6)=max{B(6),B(6-w(3))+v(3)}=max{B(6),B(2)+5}=max{7,3+5}=8;

        4) j- -即j=5,有j>w(3),则B(5)=max{B(5),B(5-w(3))+v(3)}=max{B(5),B(1)+5}=max{7,0+5}=7;

        5) j- -即j=4,有j=w(3),则B(4)=max{B(4),B(4-w(3))+v(3)}=max{B(4),B(0)+5}=max{4,0+5}=5;

        6) j- -即j=3,有j<w(3),继续访问数组会出现越界,所以本轮操作停止,B(0)到B(3)的值保留上轮循环(i=2时)的值不变,进入下一轮循环i++;

     

      如果j不逆序而采用正序j=0...capacity,如上图所示,当j=8时应该有B(8)=B(8-w(3))+v(3)=B(4)+5,然而此时的B(4)已经在j=4的时候被修改过了,原来的B(4)=4,现在B(4)=5,所以计算得出B(8)=5+5=10,显然这于正确答案不符合;所以该一维数组后面的值需要前面的值进行运算再改动,如果正序便利,则前面的值将有可能被修改掉从而造成后面数据的错误;相反如果逆序遍历,先修改后面的数据再修改前面的数据,此种情况就不会出错了;

    复制代码

     1 void FindMaxBetter()//优化空间后的动态规划
     2 {
     3     int i,j;
     4     for(i=1;i<=number;i++)
     5     {
     6         for(j=capacity;j>=0;j--)
     7         {
     8             if(B[j]<=B[j-w[i]]+v[i] && j-w[i]>=0 )//二维变一维
     9             {
    10                 B[j]=B[j-w[i]]+v[i];
    11             }
    12         }
    13     }
    14 }

    复制代码

      n) 然而不足的是,虽然优化了动态规划的空间,但是该方法不能找到最优解的解组成,因为动态规划寻早解组成一定得在确定了最优解的前提下再往回找解的构成,而优化后的动态规划只用了一维数组,之前的数据已经被覆盖掉,所以没办法寻找,所以两种方法各有其优点。

    四、蛮力法检验:

      1) 蛮力法是解决01背包问题最简单最容易的方法,但是效率很低

      2) (X1,X2,…,Xn)其中Xi=0或1表示第i件商品选或不选,共有n(n-1)/2种可能;

      3) 最简单的方式就是把所有拿商品的方式都列出来,最后再做判断此方法是否满足装包条件,并且通过比较和记录找出最优解和解组成(如果满足则记录此时的价值和装的方式,当下一次的装法优于这次,则更新记录,如此下去到最后便会找到最优解,同时解组成也找到);

      4) n件商品,共有n(n-1)/2种可能,故蛮力法的效率是指数级别的,可见效率很低;

      5) 蛮力法效率低不建议采取,但可以用于检验小规模的动态规划解背包问题的正确性和可行性,如下图输出可见,解01背包问题用动态规划是可行的:

    五、总结:

      对于01背包问题,用蛮力法与用动态规划解决得到的最优解和解组成是一致的,所以动态规划解决此类问题是可行的。动态规划效率为线性,蛮力法效率为指数型,结合以上内容和理论知识可以得出,解决此问题用动态规划比用蛮力法适合得多。对于动态规划不足的是空间开销大,数据的存储得用到二维数组;好的是,当前问题的解只与上一层的子问题的解相关,所以,可以把动态规划的空间进行优化,使得空间效率从O(n*c)转化为O(c),遗憾的是,虽然优化了空间,但优化后只能求出最优解,解组成的探索方式在该方法运行的时候已经被破坏掉;总之动态规划和优化后的动态规划各有优缺点,可以根据实际问题的需求选择不同的方式。

    六、引申:

      动态规划可以解决哪些类型的问题?

      待解决的原问题较难,但此问题可以被不断拆分成一个个小问题,而小问题的解是非常容易获得的;如果单单只是利用递归的方法来解决原问题,那么采用的是分治法的思想,动态规划具有记忆性,将子问题的解都记录下来,以免在递归的过程中重复计算,从而减少了计算量。

    展开全文
  • 基于matlab的01背包源码实现,纯手写,仅供新手学习和参考...由于代码比较简单,所以没有过多的注释,大家可以根据网上的帖子理解01背包动态规划思想,再自己临摹代码进行学习
  • 文章目录01背包问题动态规划01背包问题动态规划求解01背包问题动态规划求解-C++实现 01背包问题 有nnn个物品,这些物品的重量分别为w1,w2,...,wnw_1,w_2,...,w_nw1​,w2​,...,wn​,价值分别为v1,v2,...,vnv_1,...
  • 基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
  • 问题:有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量是 w[i],价值是 p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 举例:假设v=20,w={5,6,3,7,8},p={6,7,...
  • 本文实例讲述了C++动态规划背包问题解决方法。分享给大家供大家参考。具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3...
  • 01背包问题: 有一个背包它可以背n单位重量的物品,有几种物品它们的重量分别为1,2,3个单位,它们对应的权重分别为1500,2000,3000,求该背包怎样放物品才能使权重最大(一种物品只能放一次) 思路: 如下图用二维数组 v[i]...
  • 01背包动态规划问题。一般需要将主问题分解为多个子问题,==然后记录下不同子问题的解==,最终才能推得最终问题的答案。 2. 定义子问题:`前i件物品`恰放入一个`容量为v的背包`可以获得的==最大价值==是多少?...
  • 最早接触动态规划是在大学的算法课,当时看书遇到的第一道难题就是01背包问题,自己琢磨了半天也没想出一个好的方法,看课本几行代码就搞定了,感觉特别不可思议,当时觉得算法相当强大,不过也没太花时间在这上边,...
  • 带有贪心策略的离散粒子群算法用于求解01背包问题
  • 用c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15
  • 动态规划求解 01背包问题 java语言 1、求最优解及最优解路径 package G.C; import java.util.*; public class 动态规划01背包 { static int w[] = {0, 2,3,4,5 };//商品的体积2、3、4、5 static int v[] = {0,3,4,5,...
  • 01背包问题背包问题的区别在于,01背包,物品的选择只有两种一种是拿,另一种是不拿,而背包问题在于,物品可以只取一部分。所以01背包问题不能用贪心算法解决。 以dp[i][j]表示用i种物品,重量为j表示所取得的...
  • 动态规划背包问题——01背包

    千次阅读 2021-11-24 15:56:06
    文章目录一、01背包问题二、二维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 确定递推公式3. dp数组初始化4. 确定遍历顺序5. 举例推导dp数组三、一维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 一...
  • 本资源为 MATLAB 代码,代码中用动态规划解决了0-1背包问题。具体问题为:物品价值:v=[90 75 83 32 56 31 21 43 14 65 12 24 42 17 60];物品重量:w=[30 27 23 24 21 18 16 14 12 10 9 8 6 5 3]; 背包容量:120。...
  • * method: 动态规划(递推、递归版) * date: 2020/05/07 */ #include<iostream> #include<string.h> using namespace std; const int MAX_N=10,MAX_W=20,MAX_V=10; int dp[MAX_N][MAX_W];//记忆数组 ...
  • 动态规划法解决01背包问题(C++实现)

    千次阅读 2020-06-06 13:23:31
    问题描述:给定n种商品和一个给定固定容量的背包。物品 i 的重量是W[ i ],价值为V[ i ],背包的容量为C。问应当如何选择装入背包中的物品,使得装入背包中的物品的总价值最大? (对于同一个物品,要么放,要么不放...
  • 01背包问题 动态规划 ** 1.动态规划 什么是动态规划动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以求出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。   2.01背包...
  • 动态规划算法解01背包问题(思路及算法实现)

    万次阅读 多人点赞 2019-05-13 21:43:40
    本文相当于对教材做的一个笔记(动态规划与贪心算法解01背包必须先对背包按照单位重量的价格从大到小排序,否则拆分的子问题就不具备最优子结构的性质) 动态规划算法: 动态规划就是一个填表的过程。该表记录了已...
  • 本文主要介绍动态规划算法求解01背包问题。什么是01背包问题?什么是动态规划动态规划怎么求解01背包问题?通过阅读本文能够解答上面的三个问题。 1、什么是01背包问题01背包问题是一种比较常见的问题,例如,...
  • 01背包问题的目标是使背包中物品的价值最大。约束条件有两个:一是物品的重量不能超出背包的容量。二是物品只能整体放入背包,不能部分放入。 问题分析 (1)最优子结构 反证法 设(y1,y2,……,yn)是所给01背包问题...
  • 动态规划求解0/1背包问题

    千次阅读 多人点赞 2020-04-19 21:39:14
    一、求解0/1背包问题 1、问题描述 有n个重量分别为{w1,w2,…,wn}的物品,它们的价值分别为{v1,v2,…,vn},给定一个容量为C的背包。 设计从这些物品中选取一部分物品放入该背包的方案,每个物品要么选中要么不...
  • 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,869
精华内容 9,547
关键字:

动态规划求解01背包问题