背包九讲

0-1 背包问题

Acwing

朴素做法

状态转移方程：
定义:前i个物品，背包容量j下的最优解

• 当前背包容量不够 为前 i-1 个物品最优解：
• 当前背包容量够，判断选与不选第i个物品

选：
不选：

#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N][N];
int w[N],v[N]; // 价值 容量
int main(){
    int m,n;
    cin >> n >>m ;
    for(int i=1;i<=n;i++){
        cin >> v[i] >>w[i];
    }
    for(int i=1;i<=n;i++) // 每个物体 涉及到i-1 从1开始
        for(int j=1;j<=m;j++){  // 每个容量  涉及到i-1 从1开始
          if(j<v[i])  f[i][j] =  f[i-1][j];
          else
          f[i][j]=max(f[i-1][j],(f[i-1][j-v[i]])+w[i]); // 
        }
    cout << f[n][m];
    return 0;
}

空间优化

#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N];
int w[N],v[N]; // 价值 容量
int main(){
    int m,n;
    cin >> n >>m ;
    for(int i=1;i<=n;i++){
        cin >> v[i] >>w[i];
    }
    for(int i=1;i<=n;i++) // 每个物体 涉及到i-1 从1开始
        for(int j=m;j>=v[i];j--){  // 每个容量  涉及到i-1 从1开始
          f[j]=max(f[j],(f[j-v[i]])+w[i]); // 
        }
    cout << f[m];
    return 0;
}

完全背包问题

Acwing


详解

朴素做法

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N][N];
int v[N],w[N]; // 体积，价值
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++){
            for(int k=0;k*v[i]<=j;k++){
                dp[i][j]= max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]); // 状态转移方程
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

时间复杂度优化

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N][N];
int v[N],w[N]; // 体积，价值
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])  dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
        }
    }
    cout << dp[n][m];
    return 0;
}

空间优化最终版

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N];
int v[N],w[N]; // 体积，价值
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=v[i];j<=m;j++){  // 对应的01背包是 for(int j=m;j>=v[i];j--)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 
        }
    }
    cout << dp[m];
    return 0;
}

多重背包问题

朴素做法

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int dp[N];
int v[N],w[N],s[N]; // 体积  价值  个数
int main(){
    int  n ,m ;
    cin >> n >> m;
    for(int i =1;i<=n;i++){
        cin >> v[i]>> w[i]>> s[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
                dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout << dp[m];
    return 0;
}

二进制优化

acwing

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1010;
int dp[2001];
int v[N],w[N],s[N];// 体积 价值
const int M=15000; // 1000* lg2000
int a[M],b[M]; // 体积 价值
int main(){
    int n,m;
    cin>> n>>m;
    for(int i=1;i<=n;i++){
        cin>> v[i]>>w[i]>>s[i];
    }
    int cnt=1;
    // 对每个物体进行重组
    for(int i=1;i<=n;i++){
        for(int j=1;j<s[i];j*=2){
            s[i]-=j;
            a[cnt]=v[i]*j;
            b[cnt++]=w[i]*j;
        }
        if(s[i]>0){
            a[cnt]=v[i]*s[i];
            b[cnt++]=w[i]*s[i];
        }
    }
    //01背包
    for(int i=1;i<=cnt;i++) // 注意此时的个数变成了cnt
        for(int j=m;j>=a[i];j--){
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        }
        cout << dp[m];
    return 0;
}

分组背包问题

状态的划分：
选这组的第i个物品

#include <iostream>
#include<algorithm>
using namespace std;
const int N=102;
int dp[N];
int v[N][N],w[N][N],s[N]; // 第i组第j个物品的体积，价值；   每组的个数

int main(){
    int n,m;
    cin >> n>> m; // 组数   背包体积
    for(int i=1;i<=n;i++){
        cin >> s[i];
        for(int j=1;j<=s[i];j++)
            cin>>v[i][j] >> w[i][j];    
    }

    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            for(int k=1;k<=s[i];k++){
                if(j>=v[i][k])
                    dp[j] =max(dp[j],dp[j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout << dp[m];
    return 0;
}