背包模型基础篇

一.01背包问题

一.模型含义 :

有限个物品n和体积为V的背包,每个物品只有一个,其价值为w[i],占用体积为v[i],求出在总体积不超过V的情况下能选出的最大价值

二.注意点

01背包循环体积的时候一定要倒着循环(对于一维dp的写法,二维的随便),因为他每一轮i都要用到上一轮 i 的数据,如果正向循环会导致用到的是这一轮更新的 i. dp[i]表示的是体积不超过i的时候的最大价值

三.代码模板

#include<bits/stdc++.h>
using namespace std; 
int dp[10001];
int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        int w,v;//w是价值,w是体积,也可以提前创建数组读取
        for(int j=V;j>=v;j--)
            dp[j]=max(dp[j],dp[j-v]+w);
    //以体积为状态，当前某体积j的最大价值等于未更新时值与在从某个体积更新而来的值取max 
    } 
    cout<<dp[V];
} 

二.完全背包问题

1.模型含义

有n种物品且每种物品数量无限和体积为V的背包,占用体积为v[i]其价值为w[i],求在总体积不超过V的情况下能选出的最大价值

2.代码模板(体积的循环那里正向即可,其他的和01背包一样)

//完全背包二维写法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,V;
int v[N],w[N];
int f[N];//f[i][j]表示选前i件物品占用体积为j时物品的最大价值
int main(){
    cin>>n>>V;
    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<=V;j++){
                f[j]=max(f[j],f[j-v[i]]+w[i]);//这里的公式是可以直接背的，是同时f[i][j]和f[i][j-v[i]]推出来的 
            }
        }
    cout<<f[V];
} 

三.多重背包问题

一.模型含义

（有n种物品和体积为V的背包,每种物品的个数有限)即有限个物品n,求在总体积不超过V的情况下能选出的最大价值

二.模型+代码分析

对于朴素版:

1.f[i][j]表示的是对于第i件物品,当体积不超过j的情况下的最大价值
2.注意：V那一层的循环是从最大值到0或者从0到最大值(本质和01背包的二维写法一样),因为如果循环的时候没有写到0的话,由于f[i]由f[i-1]更新过来的,那么在上一轮没更新的f[i-1][j]中(其中j<v[i-1],所以没被更新,那就一直是0，数据得不到转移,即少了在第i-1件物品时背包太小选不了的情况)

对于二进制优化版：

1.利用二进制优化的思想,即由2^0到2^n组成的数,可以通过运算组成2^0到2^(n+1)个数,就不用暴力一个个的遍历了
2.将用二进制优化打包好的一组组数据看成是一个物品整体，使用01背包的模板解出答案

三.代码模板

朴素版(O(NVk),具体循环了多少k不知道,最差的情况会在N *V *V,如果物品体积很小的话会更大）

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int f[N][N];
int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=V;j>=0;j--){
            for(int k=0;k<=s&&k*v<=j;k++){
                //一种物品选不同个数的情况
                    f[i][j]=max(f[i][j],f[i-1][j-k*v]+w*k);
            }
        }
    }
    cout<<f[n][V];
}

二进制优化版

//二进制优化 
#include<bits/stdc++.h>
using namespace std;
const int N=12010;//注意，这里n要开到cnt那么大，一种物品可以最多有两千个的话压缩成二进制要12位，1000种物品就开开到12000以上
int f[N],v[N],w[N];
int n,V;
int main(){
    cin>>n>>V;
    int cnt=1;
    for(int i=0;i<n;i++){
        int v1,w1,s1;
        cin>>v1>>w1>>s1;
        int k=1;
        while(k<=s1){
            v[cnt]=k*v1;//二进制打包优化
            w[cnt]=w1*k;
            s1-=k;//这里不要忘了减，因为假如有s1个的话，二进制处理的部分不能超过s1，比如s1=200，那么1，2，4，...，64,我们需要看一下当前的位数能构成的最大数的多少，二进制每一位有两种选择
            k*=2;
            cnt++;
        }
        if(s1){//处理剩余的部分，2^k不能大于s1
            v[cnt]=s1*v1;
            w[cnt]=s1*w1;
            cnt++;
        }
    }
    for(int i=1;i<cnt;i++){//按照01背包处理即可
        for(int j=V;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[V];
}
//通过二进制优化，可以将中间O(s1)的复杂度优化到O(logs1),非常神奇

四.分组背包问题(一维的和01背包基本相同)

一.模型含义

一组有多个物品,每组只能选一个,求总体积不超过V的最大价值

二.代码模板

//混合背包问题一维模板(每组只能选一个，求不超过V的最大价值) 
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],s[N],v[N][N],w[N][N];//此时f[i]表示体积不超过j的最大价值 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
         cin>>v[i][j]>>w[i][j];        
        }
    }//输入每组数据 
    for(int i=1;i<=n;i++){
        for(int j=V;j>=0;j--){//只能选一个所以从大到小
            for(int k=0;k<s[i];k++)
            if(v[i][k]<=j)//因为j是>=0所以这里要给个特判防止越界 
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
     cout<<f[V];
}