背包模型进阶篇

一. 二维01背包问题

宠物小精灵之收服 : https://www.acwing.com/problem/content/1024/

一.模型定义

一维背包问题是n个物品中选,求总体积不超过V的最大价值
二维背包问题不过是多加了一个和V同属性的条件

二.代码解析

在01背包的模板下多加一层嵌套即可,其他都一样

三.AC代码

#include<bits/stdc++.h>
using namespace std;
int const N=1001;
int f[N][N];//f[i][j]表示精灵球数量花费不大于i，皮卡丘体力消耗不大于j的状态下捕获最多精灵的个数 
int main(){
    int V1,V2,n;
    cin>>V1>>V2>>n;//V1是精灵球初始数量，V2是皮卡丘初始体力 
    for(int i=0;i<n;i++){
        int v1,v2;
        cin>>v1>>v2;//v1表示需要花费的精灵球数，v2表示消耗的皮卡丘体积 
        for(int j=V1;j>=v1;j--){
            for(int h=V2-1;h>=v2;h--)//皮卡丘体力到0就不能抓精灵了所以能消耗的体力值是V2-1 
                f[j][h]=max(f[j][h],f[j-v1][h-v2]+1);
        } 
    }
    cout<<f[V1][V2-1]<<" ";
    int k=V2-1;
    while(k>0&&f[V1][V2-1]==f[V1][k-1])k--;
//一定是要和k-1比较，因为k-1是下一项，如果相等再k--,找到皮卡丘消耗的最小体力值
    cout<<V2-k; 
} 

二.方案数问题：01背包的恰好型数量问题

数字组合https://www.acwing.com/problem/content/description/280/

1.模型含义

从n个数(物品)中出恰好满足某条件的数量

2.代码分析

dp[i]表示和i的方案数

3.AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int f[N];//f[i]表示和为i的方案数
int main(){
    int n,m,v;    
    cin>>n>>m;
    f[0]=1;//和为0的情况只有一种
    for(int i=0;i<n;i++){
        cin>>v;
        for(int j=m;j>=v;j--){//01背包问题逆向循环,一个数只能用一次
            f[j]+=f[j-v];
        }
    }
    cout<<f[m];
}

//https://www.acwing.com/problem/content/280/ 
//f[j]是由f[j-v]转移过来
//处理组合问题中恰好类型的问题

三.方案数问题：完全背包的恰好型数量问题

买书 https://www.acwing.com/problem/content/1025/

一.模型含义

在n种物品,每种可以选无限多,问恰好满足某一条件的方案数

二.代码分析

dp[i][j]表示从前i件商品里选花费了j元时的方案书,对于每本书有卖和不买两种情况
注:方案书问题一定要记得初始化,且完全背包问题时正向循环

三.AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[5]={0,10,20,50,100};
int f[5][N];//f[i][j]表示从前i件商品里选花费j元时买书的方案
int main(){
    int n;
    cin>>n;//花光m元 
    f[0][0]=1;//挑0件物品花费0元的方案为1，一定要记得写 
    for(int i=1;i<=4;i++){
        for(int j=0;j<=n;j++){
            f[i][j]=f[i-1][j];//第i本书还不做选择的时候全部由上一层状态转移过来
            if(j>=v[i]){//价格不能超过j
                f[i][j]+=f[i][j-v[i]];//恰好型问题的写法 
            } 
        } 
    }
    cout<<f[4][n];//方案数肯定在最后一位 
}

补充：完全背包方案数中较难的一道题 ：
货币系统https://www.acwing.com/problem/content/534/
本题的难点在于查找数学上的一些性质,如果一个数可以有大于等于两种的方式拼凑出来,那么这个数就可以去掉

四.方案数问题：01背包的方案数问题

背包问题求方案数https://www.acwing.com/problem/content/11/

一.模型含义

01背包的背景下问最大价值的方案数

二.代码分析

同01背包的循环,当价值可以被更新的时候,转移dp数组方案数,当价值相等的时候,要累加方案数,通知最后要更新f数组

三.AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N],v[N],w[N],dp[N];//dp[i]表示最多有i的体积的时候的方案数
                         //f[i]表示的是体积不超过i的最大价值
int main(){
    int n,V;
    cin>>n>>V;
    fill(dp,dp+N,1);
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=V;j>=v[i];j--){
            if(f[j]<f[j-v[i]]+w[i])//状态可转移
            {
                dp[j]=dp[j-v[i]];
               dp[j]%=1000000007;
            }
            else if(f[j]==f[j-v[i]]+w[i])//出现结果相同的方案要叠加
             {
                  dp[j]+=dp[j-v[i]];
                  dp[j]%=1000000000+7;
             }
            f[j]=max(f[j],f[j-v[i]]+ w[i]);
        }
    }
        cout<<dp[V];
}

五.一维背包问题求具体方案

背包问题求具体方案https://www.acwing.com/problem/content/12/

一.模型含义

在一维背包的背景下求价值最大的其中一个具体方案

二.代码分析

注意：01背包问题的二维模板循环V的时候顺序无所谓但是长度一定要从0到V
在求方案数问题中,其实是一个做逆向操作的过程,看看最终的结果是如何转移回原点就可以知道该如何解了

三.代码模板

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N],w[N],v[N];
int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];    
   for (int i = n; i >= 1; i -- )
        for (int j = V; j >= 0; j -- )
        {
            f[i][j]  = f[i + 1][j];//还没选第i件的情况
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }

    int j=V;//f[1][V]这里f[1][v]为价值最大的点
    for(int i=1;i<=n;i++){//为了字典序，上面从大到小,这里从小到大
         if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])//看看f[i][j]是从哪一步转移过来的
        {
            cout << i << ' ';
            j -= v[i];
        }
    }
}