01背包题目+代码详解+一些易错点

01背包最原始题目

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000

时间复杂度o(nm),空间复杂度o(nm)
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int v[N],w[N];//储存每个物品的体积v,价值w 
int f[N][N];//记录将i个物品装入体积为j的背包的最大价值,且全局变量初始化为0,即满足边界条件,f[i][0]=f[0][j]=0,装0个物品的价值为0 
int n,m;//n个物品,最大体积为m 
int main(){
	 int n,m;
	 cin>>n>>m;
	 for(int i=1;i<=n;i++)
	 	cin>>v[i]>>w[i];
	 for(int i=1;i<=n;i++)//对于n个物品只有选或不选两种选择 
	 	for(int j=1;j<=m;j++)//记录装i个物品体积分别为1到m时的最大价值 
	 	{
	 		if(j<v[i])//如果装不了第i件物品,则f[i][j]=f[i-1][j]
	 		f[i][j]=f[i-1][j];
	 		else//如果装的了,还需比较装i-1件物品体积为j的最大价值和装i-1物品体积为j-v[i]的价值加w[i]的价值谁大 
	 		f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
	 	}
	 	cout<<f[n][m]<<endl;//最后的结果即(体积肯定最大价值才会更大)体积为m最大时,遍历完n件物品后的所能装进背包的最大价值 
}

空间复杂度优化到o(m),代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int f[N];//体积为j时的最大价值 
int v[N],w[N];
int main(){
	 cin>>n>>m;
	 for(int i=1;i<=n;i++)
	 	cin>>v[i]>>w[i];
	for(int i=1;i<=n;i++)
		for(int j=m;j>=v[i];j--)//如果顺序则右边等式为i时刻的状态,而不是i-1时刻的状态,也就是说i时刻状态可能与i-1时刻状态不同 
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		cout<<f[m]<<endl;
}

HDU2602 01背包裸题，只是多了个多组

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,t;
int v[N],w[N],f[N];
int main(){
	cin>>t;
	while(t--){
		memset(f,0,sizeof(f));
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>w[i];
		for(int i=1;i<=n;i++)
			cin>>v[i];
		for(int i=1;i<=n;i++)
			for(int j=m;j>=v[i];j--)
			   f[j]=max(f[j],f[j-v[i]]+w[i]);
			   cout<<f[m]<<endl;
	}
	return 0;
}

HDU2546 01背包需要判断一下的背包

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,f[N],w[N];//f[j]记为原始余额为j时所能花费的最大钱 
int main(){
	 while(cin>>n&&n){//输入n且n不为0 
	 	memset(f,0,sizeof(f));//多组数据一定记得初始化 
	 	memset(w,0,sizeof(w));
	 	for(int i=1;i<=n;i++)
	 		cin>>w[i];
	 	cin>>m;
		if(m<5) {//这里判断一下,如果m小于5直接输出 
			cout<<m<<endl;
			continue;
				}
		 sort(w+1,w+n+1);//排序找出价值的最大,然后用最后5块减去最大价值,剩余价值就会越少 
		 m-=5;
		 if(m>=w[1])//这里也要判断一下如果m一个都买不起就不操作,也可不判断,因为内存循环已经判断了 
		 {
		 	for(int i=1;i<n;i++)
		 		for(int j=m;j>=w[i];j--)
		 			f[j]=max(f[j],f[j-w[i]]+w[i]);//状态转移方程类比01背包 
		 }
		 printf("%d\n",m+5-f[m]-w[n]);//m-f[m]余下的钱所能买得最多的,加上5块钱-最大的 
	 } 
}

HDU1171 01背包，只是物品变成了多件，将其一个一个放入数组就OK了

#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
int f[N],n,m;
int w[55];
int a[N];
int main(){
	int sum,cnt;
	while(cin>>n&&n>=0){//结束条件 
		sum=0;//初始化 
		int k=1; 
		memset(f,0,sizeof(f));//老规矩dp多组初始化 
		for(int i=1;i<=n;i++){
			cin>>w[i]>>cnt;
			while(cnt--){
				sum+=w[i];
				a[k++]=w[i];//将所有的设备一个一个地放入数组 
			}
			}
		for(int i=1;i<k;i++)//遍历每一个设备 
			for(int j=sum/2;j>=a[i];j--)//从sum/2开始,因为要求所用设备的总金钱相差越小越好 
				f[j]=max(f[j],f[j-a[i]]+a[i]);
		printf("%d %d\n",sum-f[sum/2],f[sum/2]);//sum-f[sum/2]肯定大于等于f[sum/2] f[sum/2]用一半的钱所能买的最多设备 
		} 
	return 0; 
}

后续在更。。。。。。。。。。。。。