01背包总结+题目汇总

缺乏、安全感 2024-04-18 19:14 71阅读 0赞

我们先来理解一下01背包问题：有n种物品与承重为m的背包。每种物品只有一件，每个物品都有对应的重量weight\[i\]与价值value\[i\]，求解如何装包使得价值最大。

为什么叫它01背包呢，因为装进去就是1，不装进去就是0.所以针对每个物品就两种状态，装，不装。

所以有状态转移方程  
dp\[i\]\[j\] = max( dp\[i-1\]\[j\] , dp\[i-1\]\[ j - weight\[i\] \] + value\[i\] )  
//前一个为不装，后一个为装。

**特别注意：在01背包中，对背包容量进行遍历时，要倒序（具体请看代码）**  
01背包题目分成两类：  
1、基础题：该类型直接套模板即可，即动态转移方程dp\[j\]=max(dp\[j\],dp\[j-a\[i\]\]+b\[i\]);。如：求背包能装最大价值、装到最满、剩余最少等。  
例题：例1、2、6

2、提高题：需要转换思维，但归根结底还要依靠01背包的基础。如：求组合成某个数的方案数等。  
例题：例3、4、5、7、8、9

例1  
采药 https://www.luogu.org/problem/P1048

简单来说就是让你把背包装到价值最大  
上代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    int dp[1005],a[105],b[105];
    int main()
    {
    	int t,m;
    	cin>>t>>m;
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=m;i++)
    		cin>>a[i]>>b[i];
    	for(int i=1;i<=m;i++)//遍历物品
    	{
    		for(int j=t;j>=a[i];j--)//遍历大于该物品的背包容量（特别注意是倒序！！！）
    		{
    			dp[j]=max(dp[j],dp[j-a[i]]+b[i]);//从不取该物品、取该物品中求最大值。
    		}
    	}
    	cout<<dp[t];
    	return 0;
    }

例2  
装箱问题http://codeup.cn/problem.php?cid=100000631&pid=0  
从n件物品中，选取若干装入箱内，使箱子的剩余空间最小  
上代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    int dp[1005],a[1005]; 
    int main()
    {
    	int v,n;
    	cin>>v>>n;
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=n;i++)//遍历物品
    	{
    		for(int j=v;j>=a[i];j--)//倒序遍历箱子容量
    		{
    			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    		}
    	}
    	int ans=v-dp[v];
    	cout<<ans<<endl;
    	
     }

例3  
饭卡http://acm.hdu.edu.cn/showproblem.php?pid=2546

陷阱：  
①卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负）。所以我们要使卡里余额最小，我们首先要在现在所拥有的余额中保留5元，用这五元去购买最贵的物品，而剩下的钱就是背包的总容量，可以随意使用。  
②当输入卡上余额小于5时，直接输出余额即可。

上代码：  
\#include  
\#include  
\#include  
using namespace std;  
int cmp(int a,int b)  
\{  
return a>b;  
\}  
int dp\[1005\],a\[1005\];//dp记录消费金额  
int main()  
\{  
int n,m;  
while(cin>>n)  
\{  
memset(dp,0,sizeof(dp));  
if(n==0)  
break;  
for(int i=1;i<=n;i++)  
cin>>a\[i\];  
sort(a+1,a+1+n);//从小到大  
cin>>m;  
if(m<5)//如果钱小于5的话都不用继续操作了，直接输出m  
\{  
cout<<m<<endl;  
continue;  
\}

for(int i=1;i<n;i++)
    	{
    		for(int j=m-5;j>0;j--)
    		{
    			if(j>=a[i])//卡里有钱买 
    				dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    		}
    	}
    	int ans=m-dp[m-5]-a[n]; //先提前拿5块钱买最贵的 
    	cout<<ans<<endl;
    }

例4  
货币系统 http://codeup.cn/problem.php?cid=100000631&pid=2  
注意点：  
①初始化dp时需注意一点。凑0元时，有一种方案，即dp\[0\]=1;  
②动态转移方程：dp\[j\]=dp\[j\]+dp\[j-a\[i\]\];  
怎么理解？dp\[j\]即不选择目前选择的钱币所达到的方案数，dp\[j-a\[i\]\]为选择目前选择的钱币达到的方案数。  
上代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    long long int dp[10005],a[30];//dp存方案数，参数为钱的数值。 
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	memset(dp,0,sizeof(dp)); 
    	dp[0]=1;//凑0元时，有一种方案 
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	//完全背包问题 
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(j>=a[i])
    				dp[j]=dp[j]+dp[j-a[i]]; //不选择目前这个钱币达到j的方案+选择该钱币后能达到j的方案 
    		}
    	}
    	cout<<dp[m]<<endl;
    	return 0; 
    }

例5  
Big Event in HDU http://acm.hdu.edu.cn/showproblem.php?pid=1171  
题目看上去很复杂，其实题目对分设施就两个要求：①尽量平均分配，即差值最小 ②A>=B  
如何将差值最小转变成…最大（即简单的01背包问题）？很简单：将总价值sum求出，然后得出其分配的平均值为sum/2，这个值可看做背包大小，在这个值里，找出能分到的设施的最大值。

陷阱：当输入非正数时，程序停止！而不是n=-1!!!  
上代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int a[55],num[55],dp[1000005];
    int main()
    {
    	int n;
    	while(cin>>n&&n>=0)
    	{
    		int sum=0;
    		memset(dp,0,sizeof(dp));
    		memset(a,0,sizeof(a));
    		memset(num,0,sizeof(num));
    		for(int i=1;i<=n;i++)
    		{
    			cin>>a[i]>>num[i];
    			sum+=a[i]*num[i];
    		}
    		int mid=sum/2;
    		for(int i=1;i<=n;i++)//遍历设施
    		{
    			for(int j=1;j<=num[i];j++)//遍历每个设施的数量
    			{
    				for(int k=mid;k>0;k--)//遍历“背包”
    				{
    					if(k>=a[i])
    					{
    						dp[k]=max(dp[k],dp[k-a[i]]+a[i]);
    					}
    				}
    			}
    		}
    		int ans1=max(dp[mid],sum-dp[mid]),ans2=min(dp[mid],sum-dp[mid]);
    		cout<<ans1<<" "<<ans2<<endl;
    	}
     }

例6  
Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602  
和采药一样的基础题  
上代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int w[1005],v[1005],dp[1005];
    int main()
    {
    	int t,n,V;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n>>V;
    		memset(dp,0,sizeof(dp));
    		for(int i=1;i<=n;i++)
    			cin>>v[i];
    		for(int i=1;i<=n;i++)
    			cin>>w[i];
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=V;j>=w[i];j--)
    			{
    				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    			}
    		}
    		cout<<dp[V]<<endl;
    		
    	}
    }

例7：  
Bone Collector II http://acm.hdu.edu.cn/showproblem.php?pid=2639  
(01背包第k优解)

用个形象的比喻吧：如果我想知道学年最高分，那么，我只要知道每个班级的最高分，然后统计一遍就可以了。如果我想知道学年前十呢？我必须要知道每个班的前十名。大家在心里模拟一下，对，这就是本题核心的算法。两种决策，就可以看作这个学年只有两个班。

上代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    int n,v,k,dp[1005][50],value[105],weight[105],A[50],B[50];//dp第一个参数：容量，第二个参数：第k解 
    void k_best()
    {
    	memset(dp,0,sizeof(dp));
    	int kk;
    	for(int i=1;i<=n;i++)//遍历物品
    	{
    		for(int j=v;j>=weight[i];j--)//遍历容量
    		{
    			for(kk=1;kk<=k;kk++)//遍历第k解
    			{//把每个状态都记录下来
    				A[kk]=dp[j-weight[i]][kk]+value[i];//取当前物品的第k解
    				B[kk]=dp[j][kk];//不取当前物品
    			}
    			A[kk]=B[kk]=-1;//设一个隔板
    			int a=1,b=1,c=1;//相当于设2个指针，指向A、B
    			while(c<=k&&(A[a]!=-1||B[b]!=-1))
    			{
    				if(A[a]>B[b])
    				{
    					dp[j][c]=A[a];
    					a++;
    				}
    				else
    				{
    					dp[j][c]=B[b];
    					b++;
    				}
    				if(dp[j][c]!=dp[j][c-1])
    					c++;//如果有相同，c不变
    			}
    		}
    	}
    	cout<<dp[v][k]<<endl;;
    }
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n>>v>>k;
    		for(int i=1;i<=n;i++)
    			cin>>value[i];
    		for(int i=1;i<=n;i++)
    			cin>>weight[i];
    		k_best();
    
    	}
    }

例8  
HDU Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955

×易错思路：  
①从给定的最大被抓可能性开始遍历，忽略了概率是要相乘的。  
②计算被抓可能性。0.02\*0.02越来越小对吧？如果这样想，只要p>0.2时，无论偷多少家银行，怎么都不会被抓，所以这样想是错的。

正确思路：  
①把银行里金钱总额当做背包，偷盗成功率当做金额。求成功率>=(1-p)的最大金钱即可。

上代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct b
    {
    	int money;
    	double p;
    }bank[10005];
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int n,sum=0;
    		double p;
    		double dp[10005]={1.0};
    		cin>>p>>n;
    		p=1-p;
    		for(int i=1;i<=n;i++)
    		{
    			cin>>bank[i].money>>bank[i].p ;
    			bank[i].p = 1-bank[i].p;//偷盗成功率
    			sum+=bank[i].money;
    		}
    		for(int i=1;i<=n;i++)//遍历银行
    		{
    			for(int j=sum;j>=bank[i].money ;j--)
    			{
    				dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].p);//偷到j的最大成功率 
    			}
    		}
    		for(int i=sum;i>=0;i--)
    		{
    			if(dp[i]-p>0.000000001)//成功率>p 
    			{
    				cout<<i<<endl;
    				break;
    			}
    		 } 
    	}
    	return 0; 
    }

例9  
HDU3466 Proud Merchants http://acm.hdu.edu.cn/showproblem.php?pid=3466

题意：n个物品，m元，每个物品有价格，购买时手上最少有多少钱和价值。问m元最多买多少价值的物品。

**×**我的刚开始的错误思路：将手上最少有多少钱从大到小排序，先买要求最大的。  
错误举例：  
2 10  
8 9 2//物品A  
1 3 2//物品B  
按照我的错误思路应先买物品A,买完之后，value=2,手上的钱=2，不足以买物品B,最后总价值=3；  
若先买物品B，买完后，value=2,手上的钱=9，再买物品A,最后总价值=4.

正确思路：  
这题需要注意dp时遍历所有物品的顺序。我们考虑任意一个购买顺序，对于其中任意相邻的两个物品i，j，这两个物品的购买顺序对于后面购买的物品没有影响，因为无论前面剩下多少钱，这两个是怎样的购买顺序，最后只是消耗了pi + pj，但是会影响前面购买物品后需要剩下多少钱，假设i在j前面购买需要更少的钱，那么i在前面购买需要**pi + qj**,j在i前面购买需要**pj + qi**，**pi + qj < pj + qi 可推出qi - pi > qj - pj**，差值大的在前面购买需要前面购买后剩下较少的钱，那么对于任意相邻我们都可以做这个调换。即我们先购买q-p差值大的。  
那么在做背包时，转移方程是dp\[j\] = max(dp\[j\], dp\[j - a\[i\].p\] + a\[i\].v)，实际上对于局部j，我们考虑的是最后一次购买的是a\[i\]，然后用dp\[j - a\[i\].p\]这个量去转移，所以我们需要先用最后购买的物品去先转移dp方程。那么就是按q-p差值从小到大更新dp。

上代码：

#include<iostream>
    #include<algorithm> 
    #include<cstring>
    #include<cmath>
    using namespace std;
    int dp[50005];
    struct g{
    	int p,q,v;
    }goods[5005];
    int cmp(struct g x,struct g y)//q-p从小到大排 
    {
    	return x.q-x.p<y.q-y.p ;
    }
    int main()
    {
    	int n,m;
    	while(cin>>n>>m)
    	{
    		memset(dp,0,sizeof(dp));
    		memset(goods,0,sizeof(goods));
    		for(int i=0;i<n;i++)
    			cin>>goods[i].p>>goods[i].q>>goods[i].v;
    		sort(goods,goods+n,cmp);
    		for(int i=0;i<n;i++)
    		{
    			for(int j=m;j>=goods[i].q;j--)
    			{
    				dp[j]=max(dp[j],dp[j-goods[i].p]+goods[i].v);
    			}
    		}
    		cout<<dp[m]<<endl;
    	}
     }