01背包问题从基础到复杂

背包基础问题1

由于$\tt m\le 3$,所以可以直接枚举选哪几个物品。

#include<bits/stdc++.h>
using namespace std;
int ans = 0;
int n,m,W;
int w[101];
 
int main() {
	cin>>n>>m>>W;
	for (int i = 1; i <= n ; i ++ ) cin>>w[i];
	if (m>=1) {//只选一个物品 
		for (int i = 1; i <= n ; i ++ )
		   if (w[i]<=W) ans++;
	}
	if (m>=2) {//选两个物品(i,j) i<j
		 for (int i = 1; i <= n ; i ++ ) 
		    for (int j = i + 1; j <= n ; j ++ ) 
		       if (w[i]+w[j]<=W) ans++;
	}
	if (m==3) {
		for (int i = 1; i <= n ; i ++ )
		   for (int j = i + 1; j <= n ; j ++ )
		      for (int k = j + 1; k <= n ; k ++ )
		        if (w[i]+w[j]+w[k]<=W) ans++;
	}
	
	return 0;
}

总结

事实上是从$\tt n$个物品中选小于等于$\tt m$个物品，所以是排列组合问题中的组合问题。

背包基础问题2

第二题和第一题的差别就是我们需要开一个数组$\tt p[i]$.

• $\tt p[i]=false$ 表示i这个重量不可以达到。
• $\tt p[i]=true$ 表示i这个重量可以达到。

#include<bits/stdc++.h>
using namespace std;
int ans = 0;
int n,m,W;
int w[101];
bool p[1001];
int main() {
	freopen("a8.in","r",stdin);
	freopen("a8.out","w",stdout);
	cin>>n>>m>>W;
	p[0]=true;//背包里可以什么都不放 
	for (int i = 1; i <= n ; i ++ ) cin>>w[i];
	if (m>=1) {//只选一个物品 
		for (int i = 1; i <= n ; i ++ )
		   if (w[i]<=W) p[w[i]]=true;
	}
	if (m>=2) {//选两个物品(i,j) i<j
		 for (int i = 1; i <= n ; i ++ ) 
		    for (int j = i + 1; j <= n ; j ++ ) 
		       if (w[i]+w[j]<=W) p[w[i]+w[j]]=true;
	}
	if (m==3) {//选三个物品(i,j,k) i<j<k 
		for (int i = 1; i <= n ; i ++ )
		   for (int j = i + 1; j <= n ; j ++ )
		      for (int k = j + 1; k <= n ; k ++ )
		        if (w[i]+w[j]+w[k]<=W) p[w[i]+w[j]+w[k]]=true;
	}
	int ans = 0 ;
	for (int i = 0 ; i <= W ; i ++ ) ans+=p[i];
	cout<<ans<<endl;
	
	return 0;
}

背包基础问题3

我们开一个数组$p[i]$,表示达到重量i，所能得到的最大价值为$p[i]$.

#include<bits/stdc++.h>
using namespace std;
int ans = 0;
int n,m,W;
int w[101],v[101];
int p[1001];//p[i]表示背包里的重量i，所能得到的最大价值 
int main() {
	cin>>n>>m>>W;
	p[0]=0;//背包里可以什么都不放 
	for (int i = 1; i <= n ; i ++ ) cin>>w[i];
	for (int i = 1; i <= n ; i ++ ) cin>>v[i];
	if (m>=1) {//只选一个物品 
		for (int i = 1; i <= n ; i ++ )
		   if (w[i]<=W) {
		   	 p[w[i]]=max(p[w[i]],v[i]);
		   }
	}
	if (m>=2) {//选两个物品(i,j) i<j
		 for (int i = 1; i <= n ; i ++ ) 
		    for (int j = i + 1; j <= n ; j ++ ) 
		       if (w[i]+w[j]<=W) p[w[i]+w[j]]=max(p[w[i]+w[j]],v[i]+v[j]);
	}
	if (m==3) {//选三个物品(i,j,k) i<j<k 
		for (int i = 1; i <= n ; i ++ )
		   for (int j = i + 1; j <= n ; j ++ )
		      for (int k = j + 1; k <= n ; k ++ )
		        if (w[i]+w[j]+w[k]<=W) p[w[i]+w[j]+w[k]]=max(p[w[i]+w[j]+w[k]],v[i]+v[j]+v[k]);
	}
	int ans = 0 ;
	for (int i = 0 ; i <= W ; i ++ ) ans=max(ans,p[i]);
	cout<<ans<<endl;
	
	return 0;
}

背包问题4

$\tt x_i=0$表示第$\tt i$件物品没有在背包中。

$\tt x_i=1$表示第$\tt i$件物品在背包中。

假设有三件物品,对于$\tt x[1]=1,x[2]=0,x[3]=1$也就是说我们可以用一个二进制$(101)_2$来表示每个物品在或者没在背包。

那么本道题就是说，生成一个$x[]$数组，且保证$x[]$数组加起来的和等于$\tt m$.

$$\tt x[1]+x[2]+x[3]+...+x[n]=m$$

且要保证：

$$\tt x[1]\times w[1]+x[2]\times w[2]+...+w[n]\times x[n]\le W $$

在满足上述条件下，使得下面式子尽量大

$$\sum_{i=1}^nx_i\times p_i$$

#include<bits/stdc++.h>
using namespace std;
int n,m,W;
int w[21],p[21];
int ans=0,x[21];
void dfs(int k,int t,int now,int val) {
//k表示现在我们需要生成x[k],now表示的是已经在背包里的重量
//val表示当前背包里的价值
	if (k>n) {//x[1],x[2],...,x[n]都已经生成
		ans=max(ans,val); 
		return ;
	}	
	//x[k]=0;
	dfs(k+1,t,now,val);
	//x[k]=1放入背包
	if (now+w[k]<=W&&t<m) {
		dfs(k+1,t+1,now+w[k],val+p[k]);
	}
}
int main() {
	cin>>n>>m>>W;
	for (int i = 1; i <= n ; i ++ ) cin>>w[i];
	for (int i = 1; i <= n ; i ++ ) cin>>p[i];
	dfs(1,0,0,0);
	cout<<ans<<endl;
	return 0;
}