01背包 订阅
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。 [1] 展开全文
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。 [1]
信息
空间复杂度
O(VN)
问    题
求出获得最大价值的方案
类    别
数学问题,计算机问题
条    件
M件物品取出若干放空间W的背包里
中文名
01背包
时间复杂度
O(VN)
外文名
0-1 Knapsack
01背包背包问题
01背包题目的雏形是:有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。从这个题目中可以看出,01背包的特点就是:每种物品仅有一件,可以选择放或不放。其状态转移方程是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}对于这方方程其实并不难理解,方程之中,需要放置的是第i件物品,这件物品的体积是c[i],价值是w[i],因此f[i-1][v]代表的就是不将这件物品放入背包,而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值,比较两者的价值,得出最大的价值存入现在的背包之中。理解了这个方程后,将方程代入实际题目的应用之中,可得求出获得最大价值的方案。注意:在本题中,所有的体积值均为整数。对于背包问题,通常的处理方法是搜索。用递归来完成搜索,算法设计如下:这个算法的时间复杂度是O(n^2),我们可以做一些简单的优化。由于本题中的所有物品的体积均为整数,经过几次的选择后背包的剩余空间可能会相等,在搜索中会重复计算这些结点,所以,如果我们把搜索过程中计算过的结点的值记录下来,以保证不重复计算的话,速度就会提高很多。这是简单的“以空间换时间”。我们发现,由于这些计算过程中会出现重叠的结点,符合动态规划中子问题重叠的性质。同时,可以看出如果通过第N次选择得到的是一个最优解的话,那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。考虑用动态规划的方法来解决,这里的:阶段:在前N件物品中,选取若干件物品放入背包中状态:在前N件物品中,选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值决策:第N件物品放或者不放由此可以写出动态转移方程:我们用f[i][j]表示在前 i 件物品中选择若干件放在已用空间为 j 的背包里所能获得的最大价值这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[v];如果放第i件物品,那么问题就转化为“前i-1件物品放入已用的容量为c的背包中”,此时能获得的最大价值就是f[c]再加上通过放入第i件物品获得的价值w。这样,我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值,也就是f[m,w]算法设计如下:由于是用了一个二重循环,这个算法的时间复杂度是O(n*w)。而用搜索的时候,当出现最坏的情况,也就是所有的结点都没有重叠,那么它的时间复杂度是O(2^n)。看上去前者要快很多。但是,可以发现在搜索中计算过的结点在动态规划中也全都要计算,而且这里算得更多(有一些在最后没有派上用场的结点我们也必须计算),在这一点上好像是矛盾的。事实上,由于我们定下的前提是:所有的结点都没有重叠。也就是说,任意N件物品的重量相加都不能相等,而所有物品的重量又都是整数,那么这个时候W的最小值是:1+2+2^2+2^3+……+2^n-1=2^n -1此时n*w>2^n,动态规划比搜索还要慢~~|||||||所以,其实背包的总容量W和重叠的结点的个数是有关的。考虑能不能不计算那些多余的结点……以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢?f[v]是由f[v]和f[v-c]两个子问题递推而来,能否保证在推f[v]时(也即在第i次主循环中推f[v]时)能够得到f[v]和f[v-c]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。伪代码如下:for i=1..Nfor v=V..0f[v]=max{f[v],f[c]+w};其中的f[v]=max{f[v],f[c]}一句恰就相当于我们的转移方程f[v]=max{f[v],f[c]},因为现在的f[c]就相当于原来的f[c]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[v]由f[c]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。procedure ZeroOnePack(cost,weight)for v=V..costf[v]=max{f[v],f[v-cost]+weight}注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。有了这个过程以后,01背包问题的伪代码就可以这样写:for i=1..NZeroOnePack(c,w);我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。
收起全文
精华内容
下载资源
问答
  • 01背包

    万次阅读 2019-11-24 19:50:47
    01背包 0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 更具体的,抽象问题为: 有n个可选项,价值...

    01背包

    0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。

    问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

    更具体的,抽象问题为:

    有n个可选项,价值为vi,耗费wi,在总耗费为C的情况下选取,求总价值最大

    使用dp[i][j]表示面对第i个可选项,耗费为j时所能取到的最大值,面临的只有两种选择,取当前项,或者不取当前项:
    dp[i][j]={dp[i1][j],j<wimax(dp[i][jwi]+vi,dp[i1][j])j>=wi dp[i][j]=\begin{cases}dp[i-1][j], &\text j<wi \\ max(dp[i][j-wi]+vi,dp[i-1][j]) &\text j>=wi \end{cases}
    自底向上遍历,先遍历物品,再遍历耗费,相当于先记录下来了底层物品,低容量的记录,顶层知道记录,因此可以快速做出判断。

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=c;j++)
            {
                if(j>=w[i])
                    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
                else
                    m[i][j]=m[i-1][j];
            }
        }
    

    需要注意的是,任何动归实现时都要注意边界条件与底层条件的设置,一定要符合公式的语义

    确定能获取最大价值的选择项

    另起一个 x[ ] 数组,x[i]=0表示不拿,x[i]=1表示拿。m[n][c]为最优值,如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样,则x[n]=0 ; 否则 x[n]=1。当x[n]=0时,由m[n-1][c]继续构造最优解;当x[n]=1时,则由x[n-1][c-w[i]]继续构造最优解。以此类推,这种方式只能获取一个最优解。

        for(int i=n;i>1;i--)
        {
            if(m[i][c]==m[i-1][c])
                x[i]=0;
            else
            {
                x[i]=1;
                c-=w[i];//向下寻找
            }
        }
        x[1]=(m[1][c]>0)?1:0;//只剩下最后一个了,判断是否能拿即可
    
    展开全文
  • 01 背包

    千次阅读 2016-05-19 18:52:40
    01背包问题描述:给定 n 种物品和一背包,物品 i 的重量是 wi,其价值是 vi,背包容量为 c,问应如何选择装入背包中的物品,使装入背包中的物品价值最大?回溯法在搜索解空间树时,只要其左儿子节点是一个可行节点,...

    01背包


    问题描述:给定 n 种物品和一背包,物品 i 的重量是 wi,其价值是 vi,背包容量为 c,问应如何选择装入背包中的物品,使装入背包中的物品价值最大?


    回溯法

    在搜索解空间树时,只要其左儿子节点是一个可行节点,搜索就进入其左子树。当右子树中可能包含最优解时才进入右子树搜索。设 r 是当前剩余物品的价值总和;cv 是当前价值;max 是当前最优价值。当 cv + r <= max 时, 可减去右子树。

    void BackTrack(int cw, int cv, int i) {
        if (i > n) {
            max = cv;
            return;
        }
    
        if (cw + w[i] <= c)
            BackTrack(cw + w[i], cv + v[i], i + 1);
        if (cv + r[i + 1]  >  max)
            BackTrack(cw, cv, i + 1);
    }
    
    
    void Init() {
        for (int i = n; i >= 1; i--)        
            r[i] = r[i + 1] + v[i];
    }

    动态规划(递推法)

    正常的状态定义 d(i,j) = max{d(i+1,j), d(i+1,j-W[i]) + V[i]}
    d(i,j) 表示当前在第 i 层,背包剩余容量为 j 时的最大价值和,边界是 i > n 时 d(i,j) = 0;

    for (int i = n; i >= 1; i--)
        for (int j = 0; j <= c; j++) {
            d[i][j] = (i == n ? 0 : d[i+1][j]);
            if (j >= W[i])
                d[i][j] = max(d[i][j], d[i+1][j-W[i]] + V[i]);
        }

    对称的状态定义 f(i,j) = max{f(i-1,j), f(i-1,j-W[i]) + V[i]}
    f(i,j) 表示把前 i 个物品装到容量为 j 的背包中的最大价值和,边界是 i= 0 时 f(i,j) = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= c; j++) {
            f[i][j] = (i == 1 ? 0 : f[i-1][j]);
            if (j >= W[i])
                f[i][j] = max(f[i][j], f[i-1][j-W[i]] + V[i]);
        }

    边读边计算, 不必把 V 和 W 保存下来

    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &V, &W);
        for (int j = 0; j <= c; j++) {
            f[i][j] = (i == 1 ? 0 : f[i-1][j]);
            if (j >= W)
                f[i][j] = max(f[i][j], f[i-1][j-W] + V);
        }
    }

    滚动数组, 把数组 f 变成一维的

    memset(f, 0,  sizeof(f));
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &V, &W);
        for (int j = 0; j <= c; j++)
            if (j >= W)
                f[j] = max(f[j], f[j-W] + V);
    }
    展开全文
  • 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i(物品编号) ...

    问题描述

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

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

    i(物品编号) 1 2 3 4
    w(体积) 2 3 4 5
    v(价值) 3 4 5 6

     

    总体思路

    根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出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背包问题(最易理解的讲解)

    万次阅读 多人点赞 2012-07-06 17:09:37
    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi...

    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。

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

    f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
    Pi表示第i件物品的价值。
    决策:为了背包中物品总价值最大化,第 i件物品应该放入背包中吗 ?

    题目描述:

    假设山洞里共有a,b,c,d ,e这5件宝物(不是5种宝物),它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包, 怎么装背包,可以才能带走最多的财富。

    有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

    name weight value 1 2 3 4 5 6 7 8 9 10
    a 2 6 0 6 6 9 9 12 12 15 15 15
    b 2 3 0 3 3 6 6 9 9 9 10 11
    c 6 5 0 0 0 6 6 6 6 6 10 11
    d 5 4 0 0 0 6 6 6 6 6 10 10
    e 4 6 0 0 0 6 6 6 6 6 6 6

    只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。

    首先要明确这张表是至底向上,从左到右生成的。

    为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。

    对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。

    同理,c2=0,b2=3,a2=6。

    对于承重为8的背包,a8=15,是怎么得出的呢?

    根据01背包的状态转换方程,需要考察两个值,

    一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi;

    在这里,

     f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

    f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

    f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6

    由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包

    以下是actionscript3 的代码

    		public function get01PackageAnswer(bagItems:Array,bagSize:int):Array
    		{
    			var bagMatrix:Array=[];
    			var i:int;
    			var item:PackageItem;
    			for(i=0;i<bagItems.length;i++)
    			{
    				bagMatrix[i] = [0];
    			}
    			for(i=1;i<=bagSize;i++)
    			{
    				for(var j:int=0;j<bagItems.length;j++)
    				{
    					item = bagItems[j] as PackageItem;
    					if(item.weight > i)
    					{
    						//i背包转不下item
    						if(j==0)
    						{
    							bagMatrix[j][i] = 0;
    						}
    						else
    						{
    							bagMatrix[j][i]=bagMatrix[j-1][i];
    						}
    					}
    					else
    					{
    						//将item装入背包后的价值总和
    						var itemInBag:int;
    						if(j==0)
    						{
    							bagMatrix[j][i] = item.value;
    							continue;
    						}
    						else
    						{
    							itemInBag = bagMatrix[j-1][i-item.weight]+item.value;
    						}
    						bagMatrix[j][i] = (bagMatrix[j-1][i] > itemInBag ? bagMatrix[j-1][i] : itemInBag)
    					}
    				}
    			}
    			//find answer
    			var answers:Array=[];
    			var curSize:int = bagSize;
    			for(i=bagItems.length-1;i>=0;i--)
    			{
    				item = bagItems[i] as PackageItem;
    				if(curSize==0)
    				{
    					break;
    				}
    				if(i==0 && curSize > 0)
    				{
    					answers.push(item.name);
    					break;
    				}
    				if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)
    				{
    					answers.push(item.name);
    					curSize -= item.weight;
    				}
    			}
    			return answers;
    		}



    PackageItem类

    	public class PackageItem
    	{
    		public var name:String;
    		public var weight:int;
    		public var value:int;
    		public function PackageItem(name:String,weight:int,value:int)
    		{
    			this.name = name;
    			this.weight = weight;
    			this.value = value;
    		}
    	}

    测试代码

    				var nameArr:Array=['a','b','c','d','e'];
    				var weightArr:Array=[2,2,6,5,4];
    				var valueArr:Array=[6,3,5,4,6];
    				var bagItems:Array=[];
    				for(var i:int=0;i<nameArr.length;i++)
    				{
    					var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);
    					bagItems[i]=bagItem;
    				}
    				var arr:Array = ac.get01PackageAnswer(bagItems,10);


    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,335
精华内容 8,534
关键字:

01背包