背包问题
程序员文章站
2022-06-07 14:20:18
01背包 n个物品，v的体积，求最多能装下的价值 每个物品只能拿一次 https://www.acwing.com/problem/content/2/ 1 #include 2 using namespace std; 3 int main(){ 4 int N,V, ......
01背包
n个物品，v的体积，求最多能装下的价值
每个物品只能拿一次
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main(){
4 int n,v,dp[1005] = {0};
5 scanf("%d%d",&n,&v);
6 for(int i=1,x,y;i<=n;i++){
7 scanf("%d%d",&x,&y);
8 for(int j=v;j>=x;j--){
9 dp[j] = max(dp[j],dp[j-x]+y);
10 }
11 }
12 printf("%d\n",dp[v]);
13 return 0;
14 }
完全背包
n个物品，v的体积，求最多能装下的价值
每个物品可以拿无限次
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main(){
4 int n,v,dp[1005] = {0};
5 scanf("%d%d",&n,&v);
6 for(int i=1,x,y;i<=n;i++){
7 scanf("%d%d",&x,&y);
8 for(int j=x;j<=v;j++){
9 dp[j] = max(dp[j],dp[j-x]+y);
10 }
11 }
12 printf("%d\n",dp[v]);
13 return 0;
14 }
多重背包
n个物品，v的体积，求最多能装下的价值
每个物品可以拿ki次
一个优化：（二进制优化）
显然我们没有必要跑全ki次，判断下能用完全背包的就用完全背包好了
不能用完全背包的，考虑一个等价的次数，即，每次取1个，2个，4个。。。ki-2j+1个
j是最大的能使ki-2j+1>0的数
也就是说我们将ki二进制拆分了
时间复杂度为o(n*m*log(∑ki))
另一个优化：（单调队列优化）
————咕咕咕——————
时间复杂度o(n*m)
/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
int main(){
ll n,v,dp[20005] = {0};
scanf("%lld%lld",&n,&v);
for(ll i=1,x,y,z;i<=n;i++){
scanf("%lld%d%lld",&x,&y,&z);
if(x*z>v){
for(int j=x;j<=v;j++){
dp[j] = max(dp[j],dp[j-x]+y);
}
}else{
for(ll tmp = 1;z-tmp+1 > 0;tmp <<= 1){
ll k = (z-(tmp<<1)+1)<0?z-tmp+1:tmp;
for(ll j=v;j>=x*k;j--){
dp[j] = max(dp[j],dp[j-x*k]+y*k);
}
}
}
}
printf("%lld\n",dp[v]);
return 0;
}
混合背包
前三个混在一起，加个if判断即可
/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 2e4+7;
int dp[maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
while(n--){
int k,value,cnt;
scanf("%d%d%d",&k,&value,&cnt);
if(cnt == -1){
for(int i=m;i>=k;i--){
dp[i] = max(dp[i],dp[i-k]+value);
}
}else if(cnt == 0 || k*cnt>=m){
for(int i=k;i<=m;i++){
dp[i] = max(dp[i],dp[i-k]+value);
}
}else{
for(int i=1;cnt-i+1>0;i<<=1){
int tmp = (cnt-(i<<1)+1)<0?cnt-i+1:i;
for(int j=m;j>=tmp*k;j--){
dp[j] = max(dp[j],dp[j-tmp*k]+tmp*value);
}
}
}
}
printf("%d\n", dp[m]);
return 0;
}
二维费用的背包问题
物体不止有体积这个限制条件，还有质量这个限制条件
n个物体，v的背包容积，m的负重限制，还是01背包只能拿一个
/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 1e3+7;
int dp[maxn][maxn];
int main(){
int n,v,m;
scanf("%d%d%d",&n,&v,&m);
while(n--){
int volum,weight,value;
scanf("%d%d%d",&volum,&weight,&value);
for(int i=v;i>=volum;i--){
for(int j=m;j>=weight;j--){
dp[i][j] = max(dp[i][j],dp[i-volum][j-weight]+value);
}
}
}
printf("%d\n",dp[v][m]);
return 0;
}
分组背包问题
每组只能拿一个，这样调整下for的顺序就好了
/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 1e3+7;
int dp[maxn];
int weight[maxn],value[maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
while(n--){
int cnt;
scanf("%d",&cnt);
for(int i=1;i<=cnt;i++){
scanf("%d%d",&weight[i],&value[i]);
}
for(int i=m;i>=0;i--){
for(int j=1;j<=cnt;j++)if(i>=weight[j]){
dp[i] = max(dp[i],dp[i-weight[j]]+value[j]);
}
}
}
printf("%d\n",dp[m]);
return 0;
}
有依赖的背包问题
要想拿当前物体，必须拿它的父亲
用dfs先处理处子节点，然后拿出当前节点（因为必须拿当前才能拿子节点）
做一个背包，然后把当前节点更新进去
/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 107;
int n,m,root;
int head[maxn],to[maxn],next[maxn],tot = 1;
int dp[maxn][maxn],val[maxn],wei[maxn];
void add(int u,int v){
to[tot] = v;
next[tot] = head[u];
head[u] = tot++;
}
void dfs(int u){
for(int i=head[u];i;i=next[i]){
int son = to[i];
dfs(son);
for(int j=m-wei[u];j>=wei[son];j--){
for(int k=wei[son];k<=j;k++){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[son][k]);
}
}
}
for(int i=m;i>=wei[u];i--)dp[u][i] = dp[u][i-wei[u]]+val[u];
for(int i=0;i<wei[u];i++)dp[u][i] = 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++){
scanf("%d%d%d",&wei[i],&val[i],&x);
if(~x)add(x,i);
else root = i;
}
dfs(root);
printf("%d\n",dp[root][m]);
return 0;
}
背包问题求方案数
加一个数组，更新即可
/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod = 1e9+7;
int n,m;
int dp[maxn],ans[maxn];
int main(){
scanf("%d%d",&n,&m);
fill(ans,ans+n,1);
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
for(int j=m;j>=x;j--){
if(dp[j]<dp[j-x]+y){
ans[j] = ans[j-x];
}else if(dp[j] == dp[j-x]+y){
ans[j] += ans[j-x];
ans[j] %= mod;
}
dp[j] = max(dp[j],dp[j-x]+y);
}
}
printf("%d\n",ans[m]);
return 0;
}
背包问题求具体方案
求字典序最小的方案
倒着来一遍背包，然后正着扫描一遍
/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 1e3+7,mod = 1e9+7;
int n,m;
int dp[maxn][maxn];
int x[maxn],y[maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=n;i>=1;i--){
for(int j=0;j<x[i];j++)
dp[i][j] = dp[i+1][j];
for(int j=x[i];j<=m;j++)
dp[i][j] = max(dp[i+1][j],(dp[i+1][j-x[i]]+y[i]));
}
for(int i=1;i<=n;i++){
if(m>=x[i] && dp[i][m] == dp[i+1][m-x[i]]+y[i]){
printf("%d ",i);
m -= x[i];
}
}
return 0;
}