关于01背包的DP题目代码详解+一些易错点
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;
}
后续在更。。。。。。。。。。。。。
