完全背包问题

桃扇骨 2022-05-06 15:27 245阅读 0赞

完全背包问题跟01背包的区别是01背包每个物品只能选一次，总共就这几个。

而完全背包问题是每个物品可以无限选，只要装得下。可以看成是有几种物品，每种都无限多个。

可以在01背包的基础上进行改动：[总结——01背包问题 （动态规划算法）][01_]

01背包在选第i个物品时，容积够用情况下，只有2种状态可选，放还是不放，找出最大价值的选择。

而完全背包在选第i种物品时，容积够用情况下，可能有2种以上状态可选，放1个，或者2个，3个......，或者不放。

找出最大价值的选择

代码如下：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int main()
    {
    	int i,j,k;
    	int m[20];//容量为c时，用来存储第i件物品，放入几件 
        int dp[20][20],x[20];
        int v[]={0,8,10,6,3,7,2}; ///为便于读者阅读，初始化
        int w[]={0,4,6,9,2,5,1};
        int n=6,c=19;
     
        memset(dp,0,sizeof(dp));
        memset(x,0,sizeof(x));
        int tmp;
        for(i=1;i<=n;i++)
        {
        	for(j=1;j<=c;j++)//在背包容量为j的情况下，从1~i中挑选物体，使得总价值最大 
        	{
        		if(j>=w[i])//在背包全空的情况下，判断能不能融入新的物品
        		{	
        			tmp=dp[i-1][j];
        			for(k=1;k<=j/w[i];k++)//看下到底可以装入几个
    				{
    					//tmp=max(tmp,dp[i-1][j-k*w[i]]+k*v[i]);//第二步思路 
    					if(tmp<dp[i-1][j-k*w[i]]+k*v[i])//第三步思路 
    					{
    						tmp=dp[i-1][j-k*w[i]]+k*v[i];
    						if(j==c)
    							m[i]=k; 
    					}
    					//dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]);//第一步思路 
    				} 
        			dp[i][j]=tmp;
    			}		
    			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-=m[i]*w[i];//这里不知道装了几个，不知道减几个W[i] 
    		} 
    	}
    	
    	for(i=1;i<=n;i++)
    	{
    		if(x[i]!=0)
    			cout<<"物品"<<i<<"有"<<m[i]<<"个"<<endl;
    	}
    	
    	
    	cout<<endl<<dp[n][c]<<endl;//输出背包容量为c,装前n中物品的最大价值 
    	return 0;
    	
    }

![70][]

利用上面的处理方法，也很容易求得多重背包的问题。

[01_]: https://blog.csdn.net/xp731574722/article/details/70766804
[70]: /images/20220506/28bf847924f142ccbf97a2a025e7da04.png