当前位置：首页 > news >正文

算法知识点————背包问题

news 来源：原创 2024/9/20 14:51:17

万能头文件#include<bits/stdc++.h>

01 背包

定义：物品只能用1次。01对应选还是不选第i个物品 .N个物品、V容量的最大价值。
思路：
（1）f[ i ] [j] 表示前i个物品容量j的最大价值。

（2）当前背包容量不够（j < V[i]），不能选i了，此时最大价值是前i-1和物品的最大价值。f[i] [j] = f[i-1] [j]

(3) 容量够用。可以选i也可以不选i。

选i。f[i] [j] = f[i-1] [j-V[i]] + w[i]

不选i。f[i] [j] = f[i-1] [j]

这两种情况取最值max()

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX][MAXX];//f[i][j] 前i个物品容量j的最大价值
int v[MAXX]; // 体积
int w[MAXX]; // 价值
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++){for(int j=1;j<=m;j++){if(j < v[i]){//此时不能装下第i个物品，最优解是前i-1的最优解f[i][j] = f[i-1][j];}else{f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i]);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的}}}cout<<f[n][m]<<endl;return 0;
}

优化：成一维

（1） f[j] 容量j下的最优解

（2）这里的j应该逆序更新

（3） f[j] = max(f[j] , f[j-v[i] ] + w[i] )

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];//f[j] 容量j的最大价值
int v[MAXX]; // 体积
int w[MAXX]; // 价值
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++){//for(int j=m;j>=0;j--){for(int j=m;j>= v[i];j--){//if(j < v[i]){//此时不能装下第i个物品，最优解是前i-1的最优解// f[j] = f[j];// }else{f[j] = max(f[j],f[j-v[i]] + w[i]);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的// }}}cout<<f[m]<<endl;return 0;
}

优化输入

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];//f[j] 容量j的最大价值
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++){int v,w;cin>>v>>w;//一边输入一边处理for(int j=m;j>= v;j--){f[j] = max(f[j],f[j-v] + w);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的}}cout<<f[m]<<endl;return 0;
}

完全背包问题

定义：每种物品都有无限件可用。

一维结论是for(int j=m;j>= v[i];j–){这里面是正向for(int j=v[i] ;j<=m;j++)

01背包区别：f[i] [j] = max(f[i-1] [j] , f[i-1] [j-v[i]] +w[i])

完全背包区别：f[i] [j] = max(f[i-1] [j] ,f[i] [j-v[i]] +w[i])

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];
int v[MAXX];
int w[MAXX];
int main(){int n,m;cin>>n>>m;for(int i=0; i<n; i++){cin>>v[i]>>w[i];}for(int i=0;i<n;i++){for(int j=v[i];j<=m;j++){//这里正序f[j] = max(f[j],f[j-v[i]] + w[i]);}}cout<<f[m]<<endl;return 0;
}