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-09-26 09:38:21
    01背包,有件物品和一个容量为V的背包。放入第件物品耗费的费用是,得到的价值是。求解将哪些物品装入背包可使价值总和最大。 例题 采药 思路 对于01背包问题中的每一种物品都有取或不取两种选择:取或不取。...

    问题模板      

     01背包,有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是W_{i},得到的价值是V_{i}^{}。求解将哪些物品装入背包可使价值总和最大。     

    例题 

    采药

    思路

    对于01背包问题中的每一种物品都有取或不取两种选择:取或不取。对于子问题定义状态:即F[i,v]表示前i件物品恰好放入一个容器为v的背包可以获得的最大价值。则其状态转移方程为:

                                                F[i,v]=max(F[i-1,v],F[i-1,v-W_{i}]+V_{i})

    源码

    内存不压缩版本:

    #include<iostream>
    using namespace std;
    
    #define ll long long
    
    const int MAXN=111;
    int t,m; 
    int a[MAXN],b[MAXN];
    int f[1010][1010];
    int read(){
    	int f=1,ans=0;
    	char c;
    	c=getchar();
    	while(!isdigit(c)){
    		if(c=='-') f=-1;
    		c=getchar();
    	}
    	while(isdigit(c)){
    		ans=ans*10+c-'0';
    		c=getchar();
    	}
    	return f*ans;
    }
    int main() {
    
    	t=read();
    	m=read();
    	for(int i=1;i<=m;i++) a[i]=read(),b[i]=read();
    	for(int i=1;i<=m;i++){
    		for(int j=t;j>=0;j--){
    			if(j>=a[i]){
    				f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
    			}else{
    				f[i][j]=f[i-1][j];
    			}
    		}
    	}
    	cout<<f[m][t];	
    	return 0;
    }
    

    内存压缩版本:

    #include<iostream>
    
    using namespace std;
    
    const int MAXN=111;
    
    int t,m; 
    int a[MAXN],b[MAXN];
    int f[1010];
    int read(){
    	int f=1,ans=0;
    	char c;
    	c=getchar();
    	while(!isdigit(c)){
    		if(c=='-') f=-1;
    		c=getchar();
    	}
    	while(isdigit(c)){
    		ans=ans*10+c-'0';
    		c=getchar();
    	}
    	return f*ans;
    }
    int main() {
    	t=read();
    	m=read();
    	for(int i=1;i<=m;i++) a[i]=read(),b[i]=read();
    	for(int i=1;i<=m;i++){
    		for(int j=t;j>=0;j--){
    			if(j>=a[i]){
    				f[j]=max(f[j],f[j-a[i]]+b[i]);
    			}
    		}
    	}
    	cout<<f[t];	
    	return 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(物品编号)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背包问题

    万次阅读 多人点赞 2018-03-02 13:53:57
    【回溯法】--01背包问题1、问题描述 给定n种物品和一背包。物品i的重量是wi&gt;0,其价值为vi&gt;0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? (要求使用回溯法...

    【回溯法】--01背包问题

    1、问题描述

      给定n种物品和一背包。物品i的重量是wi>0,其价值为vi>0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? (要求使用回溯法)

     例如:

    2、算法分析

    【整体思路】

      01背包属于找最优解问题,用回溯法需要构造解的子集树。对于每一个物品i,对于该物品只有选与不选2个决策,总共有n个物品,可以顺序依次考虑每个物品,这样就形成了一棵解空间树: 基本思想就是遍历这棵树,以枚举所有情况,最后进行判断,如果重量不超过背包容量,且价值最大的话,该方案就是最后的答案。

          在搜索状态空间树时,只要左子节点是可一个可行结点,搜索就进入其左子树。对于右子树时,先计算上界函数,以判断是否将其减去(剪枝)。

      上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。 

        为了更好地计算和运用上界函数剪枝,选择先将物品按照其单位重量价值从大到小排序,此后就按照顺序考虑各个物品。

    【举例说明】

      对于n=4的0/1背包问题,其解空间树如图所示,树中的16个叶子结点分别代表该问题的16个可能解。 

    【算法设计】

        利用回溯法试设计一个算法求出0-1背包问题的解,也就是求出一个解向量xi (即对n个物品放或不放的一种的方案)

     其中, (xi = 0 或1,xi = 0表示物体i不放入背包,xi =1表示把物体i放入背包)。

    在递归函数Backtrack中,
        当i>n时,算法搜索至叶子结点,得到一个新的物品装包方案。此时算法适时更新当前的最优价值
        当i<n时,当前扩展结点位于排列树的第(i-1)层,此时算法选择下一个要安排的物品,以深度优先方式递归的对相应的子树进行搜索,对不满足上界约束的结点,则剪去相应的子树。

    【时间复杂度&&优化】  

      因为物品只有选与不选2个决策,而总共有n个物品,所以时间复杂度为

      因为递归栈最多达到n层,而且存储所有物品的信息也只需要常数个一维数组,所以最终的空间复杂度为O(n)。

    相关链接1

    相关链接2

    相关链接3

    【源代码】        

    #include <iostream>
    #include <stdio.h>
    //#include <conio.h>
    using namespace std;
    int n;//物品数量
    double c;//背包容量
    double v[100];//各个物品的价值 value
    double w[100];//各个物品的重量 weight
    double cw = 0.0;//当前背包重量 current weight
    double cp = 0.0;//当前背包中物品总价值 current value
    double bestp = 0.0;//当前最优价值best price
    double perp[100];//单位物品价值(排序后) per price
    int order[100];//物品编号
    int put[100];//设置是否装入,为1的时候表示选择该组数据装入,为0的表示不选择该组数据
    
    
    //按单位价值排序
    void knapsack()
    {
        int i,j;
        int temporder = 0;
        double temp = 0.0;
    
        for(i=1;i<=n;i++)
            perp[i]=v[i]/w[i]; //计算单位价值(单位重量的物品价值)
        for(i=1;i<=n-1;i++)
        {
            for(j=i+1;j<=n;j++)
                if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
            {
                temp = perp[i];  //冒泡对perp[]排序
                perp[i]=perp[j];
                perp[j]=temp;
    
                temporder=order[i];//冒泡对order[]排序
                order[i]=order[j];
                order[j]=temporder;
    
                temp = v[i];//冒泡对v[]排序
                v[i]=v[j];
                v[j]=temp;
    
                temp=w[i];//冒泡对w[]排序
                w[i]=w[j];
                w[j]=temp;
            }
        }
    }
    
    //回溯函数
    void backtrack(int i)
    {   //i用来指示到达的层数(第几步,从0开始),同时也指示当前选择玩了几个物品
        double bound(int i);
        if(i>n) //递归结束的判定条件
        {
            bestp = cp;
            return;
        }
        //如若左子节点可行,则直接搜索左子树;
        //对于右子树,先计算上界函数,以判断是否将其减去
        if(cw+w[i]<=c)//将物品i放入背包,搜索左子树
        {
            cw+=w[i];//同步更新当前背包的重量
            cp+=v[i];//同步更新当前背包的总价值
            put[i]=1;
            backtrack(i+1);//深度搜索进入下一层
            cw-=w[i];//回溯复原
            cp-=v[i];//回溯复原
        }
        if(bound(i+1)>bestp)//如若符合条件则搜索右子树
            backtrack(i+1);
    }
    
    //计算上界函数,功能为剪枝
    double bound(int i)
    {   //判断当前背包的总价值cp+剩余容量可容纳的最大价值<=当前最优价值
        double leftw= c-cw;//剩余背包容量
        double b = cp;//记录当前背包的总价值cp,最后求上界
        //以物品单位重量价值递减次序装入物品
        while(i<=n && w[i]<=leftw)
        {
            leftw-=w[i];
            b+=v[i];
            i++;
        }
        //装满背包
        if(i<=n)
            b+=v[i]/w[i]*leftw;
        return b;//返回计算出的上界
    
    }
    
    
    
    int main()
    {
        int i;
        printf("请输入物品的数量和背包的容量:");
        scanf("%d %lf",&n,&c);
        /*printf("请输入物品的重量和价值:\n");
        for(i=1;i<=n;i++)
        {
            printf("第%d个物品的重量:",i);
            scanf("%lf",&w[i]);
            printf("第%d个物品的价值是:",i);
            scanf("%lf",&v[i]);
            order[i]=i;
        }*/
        printf("请依次输入%d个物品的重量:\n",n);
        for(i=1;i<=n;i++){
            scanf("%lf",&w[i]);
            order[i]=i;
        }
    
        printf("请依次输入%d个物品的价值:\n",n);
        for(i=1;i<=n;i++){
            scanf("%lf",&v[i]);
        }
    
    
        knapsack();
        backtrack(1);
    
    
        printf("最优价值为:%lf\n",bestp);
        printf("需要装入的物品编号是:");
        for(i=1;i<=n;i++)
        {
            if(put[i]==1)
                printf("%d ",order[i]);
        }
        return 0;
    }

     

    展开全文
  • 课程作业,实现算法实践书后的例题,实现01背包问题
  • C++动态规划实现01背包算法入门通过二维表的方式实现01背包的选取问题
  • 01背包和部分背包

    2017-11-13 14:39:58
    C语言写的01背包问题和部分背包问题的算法设计文档,内容详实
  • 动态规划之01背包问题(最易理解的讲解)

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

    2017-11-09 21:38:32
    01背包例题01背包例题01背包例题01背包例题01背包例题01背包例题
  • 01背包问题 图解+详细解析 (转载)

    万次阅读 多人点赞 2019-08-10 17:06:13
    (原文写的非常棒,算法...有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,cap...
  • 01背包问题

    2017-12-19 21:52:16
    01背包问题 。
  • 免疫克隆解决01背包问题,将免疫概念及其理论应用于遗传算法,在保留原算法优良特性的前提下,力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象,这种算法称为免疫算法...
  • 01背包问题是背包类问题中最基本的问题,其它各类背包问题都是在其基础上演变而来 牢记01背包的特点:每一件物品至多只能选一件,即在背包中该物品数量只有0和1两种情况 装入背包,如果装不下就换下一个,直到包满...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,922
精华内容 17,968
关键字:

01背包