01背包问题

怼烎@ 2022-05-06 15:00 292阅读 0赞

转载：[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp731574722_article_details_70766804]

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

问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

分析一波，面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。

解决办法：声明一个 大小为  m\[n\]\[c\] 的二维数组，m\[ i \]\[ j \] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m\[i\]\[j\] 的计算方法，

（1）. j < w\[i\] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿

m\[ i \]\[ j \] = m\[ i-1 \]\[ j \]

（2）. j>=w\[i\] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取，m\[ i \]\[ j \]=m\[ i-1 \]\[ j-w\[ i \] \] + v\[ i \]。 这里的m\[ i-1 \]\[ j-w\[ i \] \]指的就是考虑了i-1件物品，背包容量为j-w\[i\]时的最大价值，也是相当于为第i件物品腾出了w\[i\]的空间。

如果不拿，m\[ i \]\[ j \] = m\[ i-1 \]\[ j \] , 同（1）

究竟是拿还是不拿，自然是比较这两种情况那种价值最大。

由此可以得到状态转移方程：

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];

例：0-1背包问题。在使用动态规划算法求解0-1背包问题时，使用二维数组m\[i\]\[j\]存储背包剩余容量为j，可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制

价值数组v = \{8, 10, 6, 3, 7, 2\}，

重量数组w = \{4, 6, 2, 2, 5, 1\}，

背包容量C = 12时对应的m\[i\]\[j\]数组。

![70][]

(第一行和第一列为序号，其数值为0)  
如m\[2\]\[6\],在面对第二件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第一件物品的价值8，如果拿，就要把第一件物品拿出来，放第二件物品，价值10，那我们当然是选择拿。m\[2\]\[6\]=m\[1\]\[0\]+10=0+10=10;依次类推，得到m\[6\]\[12\]就是考虑所有物品，背包容量为C时的最大价值。

#include <iostream>
        #include <cstring>
        using namespace std;
         
         
        const int N=15;
         
         
        int main()
        {
            int v[N]={0,8,10,6,3,7,2};
            int w[N]={0,4,6,2,2,5,1};
         
         
            int m[N][N];
            int n=6,c=12;
            memset(m,0,sizeof(m));
            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];
                }
            }
         
         
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=c;j++)
                {
                    cout<<m[i][j]<<' ';
                }
                cout<<endl;
            }
         
         
            return 0;
        }

到这一步，可以确定的是可能获得的最大价值，但是我们并不清楚具体选择哪几样物品能获得最大价值。

另起一个 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时，由x\[n-1\]\[c\]继续构造最优解；当x\[n\]=1时，则由x\[n-1\]\[c-w\[i\]\]继续构造最优解。以此类推，可构造出所有的最优解。（这段全抄算法书，实在不知道咋解释啊。。）

void traceback()
    {
        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;
    }

如果能看懂，会觉得上面讲的挺透彻。看不懂得话，找些视频，先把那表格和状态转移方程理解透。

下面是我自己写了一遍的代码：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int main()
    {
    	int i,j;
        int dp[20][20],x[20];
        int v[]={0,8,10,6,3,7,2}; ///为便于读者阅读，初始化
        int w[]={0,4,6,2,2,5,1};
        int n=6,c=12;
     
        memset(dp,0,sizeof(dp));
        memset(x,0,sizeof(x));
        for(i=1;i<=n;i++)
        {
        	for(j=1;j<=c;j++)//在背包容量为j的情况下，从1~i中挑选物体，使得总价值最大 
        	{
        		if(j>=w[i])//在背包全空的情况下，判断能不能融入新的物品
    				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    				//最后一个不放入，和放入的情况。
    			    //上面这句话，非常重要 
    			else
    				dp[i][j]=dp[i-1][j]; 
    		}
    	}
    	
    
    	for(i=1;i<=n;i++)
    	{
    		for(j=1;j<=c;j++)
    			printf("%3d",dp[i][j]);
    		cout<<endl;
    	}
    	
    	int tmpc=c;
    	for(i=n;i>0;i--)
    	{
    		if(dp[i][tmpc]==dp[i-1][tmpc])//表示没装入 
    			x[i]=0;
    		else
    		{
    			x[i]=1;
    			tmpc-=w[i];
    		} 
    	}
    	
    	for(i=1;i<=n;i++)
    	{
    		if(x[i]!=0)
    			cout<<i<<" ";
    	}

[https_blog.csdn.net_xp731574722_article_details_70766804]: https://blog.csdn.net/xp731574722/article/details/70766804
[70]: /images/20220506/b10c59141000426da7f77d99647c9dad.png