背包问题复习题单讲解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

背包问题复习题单讲解

作者：

渔枫向晚 , 2022-04-18 00:14:22 , 所有人可见 , 阅读 511

5

10

题单

基础应用
1. 5 倍经验日 01背包基础应用
2. 二维费用背包问题 01背包拓展
3. 宠物小精灵之收服基础背包模型应用
4. Cow Frisbee Team S
背包问题演变问题
1. 数字组合 01背包求方案数
2. 货币系统完全背包求方案数
3. 货币系统完全背包求最大无关向量组个数
4. 机器分配背包问题输出方案
5. 背包问题求具体方案
6. 背包问题求方案数
细节极优化
1. 潜水员初始化对求解的重要性
2. 多重背包问题 III 单调队列优化
树上背包问题
1. 金明的预算方案树上背包铺垫
2. 有依赖的背包问题树上背包铺垫
背包建模
1. 混合背包问题混合背包模型
2. CF730J Bottles 01背包建模 + 贪心
3. 能量石背包建模 + 贪心
4. 垃圾陷阱背包建模
5. 排兵布阵分组背包建模
6. Cow Exhibition G 背包问题建模
7. 飞扬的小鸟背包建模 01背包 + 完全背包

1.基础应用

2.演变问题

3.细节和优化

4.树上背包问题

5.背包建模问题

5.1 混合背包问题

题意

$\space\space\space\space\space$ 本题考查混合背包的基础应用需要注意的是对多重背包我们需要进行二进制优化不然容易导致TLE 然后分别讨论即可

源码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;


int n, m;
int f[N];


void O_bag(int v, int w)// 01背包
{
    for(int i = m; i >= v; i --)
       f[i] = max(f[i], f[i - v] + w);
}

void comp_bag(int v, int w) //完全背包
{
    for(int i = v; i <= m; i ++)
      f[i] = max(f[i], f[i - v] + w);
}

void Re_bag(int vi, int wi, int si) //多重背包 二进制优化枚举
{
    int v[N], w[N];
    int cnt = 0;
    for(int i = 1; i <= si; i <<= 1)
    {
        v[++ cnt] = vi * i;
        w[cnt] = wi * i;
        si -= i;
    }
    if(si > 0)
    {
        v[++ cnt] = vi * si;
        w[cnt] = wi * si;
    }

    for(int i = 1; i <= cnt; i ++)
       for(int j = m; j >= v[i]; j --)
         f[j] = max(f[j], f[j - v[i]] + w[i]);

}

int main()
{
    cin >> n >> m;
    int vi, wi, si;

    for(int i = 1; i <= n; i ++)
    {
        cin >> vi >> wi >> si;
        if(si == -1) O_bag(vi, wi);
        else if(si == 0) comp_bag(vi, wi);
        else Re_bag(vi, wi, si);
    }
    cout <<f[m] << endl;
}

5.2CF730J Bottles

题意

$\space\space\space\space\space$ 求有 n 瓶水，第 i 瓶水的水量为 $a_i$ 容量为 $b_i$ 将 1 单位水从一个瓶子转移到另一个瓶子所消耗时间为 1 秒，且可以进行无限次转移。求储存所有水所需最小瓶子数 k 以及该情况下所用最小时间 t

分析

$\space\space\space\space\space$ 对于第一问我们很显然的知道所需要的最少瓶子数就是选举构成总体积为原来所有水瓶的体积和的最少瓶子数
$\space\space\space\space\space$ f[i][j][k]表示在前i个瓶子中在总容量恰好为j的时侯选取k个瓶子下的容积最大
需要注意的是本题我们是恰好所以针对初始化需要特定进行初始

memset(f, -0x3f, sizeof f);
f[0][0] = 0;

$\space\space\space\space\space$ 我们为什么要将其余值赋值为负极值因为在本题中我们是恰好方案也就对应了某些情况是不存在的比如体积为1 3 4 是构造不出2这种情况所以我们将其赋值为负极值代表这种情况不存在然后我们将0赋值为0 代表从0进行转移

源码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define endl '\n'
const int N = 110, INF = 1e9 + 7;

int f[N * N][N];
struct Node
{
    int a, b;
}q[N];
bool cmp(Node x, Node y)
{
    return x.b > y.b;
}

int n, m;

int main()
{
    cin >> n;
    int suma = 0;
    for(int i = 1; i <= n; i ++) cin >> q[i].a, suma += q[i].a;

    for(int i = 1; i <= n; i ++) cin >> q[i].b;
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    sort(q + 1, q + n + 1, cmp);
    int res = 0, sum = 0;


   while(sum < suma) sum += q[++ res].b; 

   cout << res <<" ";

    for(int i = 1; i <= n; i ++)
      for(int j = sum; j >= q[i].b; j --)
        for(int k = 1; k <= res; k ++)
          f[j][k] = max(f[j][k], f[j - q[i].b][k - 1] + q[i].a);

    int ans = 0;

    for(int i = suma; i <= sum; i ++)
       ans = max(ans, f[i][res]);

    cout << suma - ans;   
}

5.3能量石

分析

能量石.png
$\space\space\space\space\space$ 所以我们对其进行排序优化选择顺序后进行背包决策判断即可

本题同样是恰好问题我们需要初始化为所有为极值

源码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10010;

struct Node
{
    int e, s, l;
}q[N];

bool cmp(Node a, Node b)
{
    return a.s * b.l < b.s * a.l;
}
int n;
int f[N];

void solve()
{
    cin >> n;
    int m = 0;
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    for(int i = 0; i < n; i ++) cin >> q[i].s >> q[i].e >> q[i].l, m += q[i].s;

    sort(q, q + n, cmp);




    for(int i = 0; i < n; i ++)
      for(int j = m; j >= q[i].s; j --)
         f[j] = max(f[j], f[j - q[i].s] + q[i].e - (j - q[i].s) * q[i].l);


    int res = 0;
    for(int i = 0; i <= m; i ++) res = max(res, f[i]);
    cout << res << endl;
}


int main()
{
    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++)
    {
        cout <<"Case #"<<i<<": ";
        solve();
    }
}

5.4垃圾陷阱

题意

$\space\space\space\space\space$ 给定n个按照时间出现物品每个物品可以选择作为增加生命值或者选择进行高度增加要你判断能否在死亡前达到给定高度如果能输出最短时间反之输出维持的最大时间

分析

$\space\space\space\space\space$ 本题我们发现需要逐一对每项物品进行01决策判断所以我们推断是一道背包dp题那么我们需要考虑体积和价值分别是什么我们发现本题可能作为状态的选择总共有四种：高度生命物品和时间接着我们发现我们一定是按照时间来进行每个物品的选举顺序所以时间是个干扰量主要是个排序前提接着我们最后只需要判断高度和生命即可我们发现如果j代表时间 f[i][j]代表前i个物品在j时间下的高度我们尝试写出转移方程判断每个物品增加生命或者增加高度
$f[i][j] = max(f[i - 1][j] + q[i].h, f[i - 1][j - q[i].c])$
我们发现鉴于这种情况的划分在最后的判断跳出的最小时间以及对j的遍历中我们均不好操作所以我们采取第二种建模我们将j赋值为高度而时间则变f[][]表示值则装态方程
$f[i][j ] = max(f[i - 1][j] + q[i].c, f[i - 1][j - q[i].h])$
为什么这样是正确的(因为题意要求的是时间所以我们将时间赋值给f[]数组) 我们将题意转化下 垃圾的高度-> 体积存活的时间 -> 价值即求体积被塞满或者塞爆时候的最小价值此时则一目了然所以在背包的建模中我们一定要判断清楚每个状态的划分优劣进而选择最好的状态表示常规来说我们的f[]数组更多的是题意最后要询问的元素

本题涉及刷表法该方法未学透彻待填

源码

//建模  垃圾的高度-> 体积 存活的时间 -> 价值 即求体积被塞满或者塞爆时候的最小价值

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

#define endl '\n'
const int N = 3e3 + 10, INF = 1e9 + 7;

int h, n;

string s;
struct Node
{
    int t, v, h;
}q[N];

bool cmp(Node a, Node b)
{
    return a.t < b.t;
}
int f[N][N]; // 枚举到第i个垃圾 且高度为j的时候的最大存活时间

int main()
{
    cin >> h >> n;

    for(int i = 1; i <= n; i ++) cin >> q[i].t >> q[i].v >> q[i].h;

    sort(q + 1, q + n + 1, cmp);

    memset(f, -0x3f, sizeof f);
    f[0][0] = 10;
    int res = 10;
    for(int i = 1; i <= n; i ++)
    {

        int cur = i & 1, pre = cur ^ 1;
        memset(f[cur], -0x3f, sizeof f[cur]);
        for(int j = h; j >= 0; j --)
       {   

            if(f[pre][j] < q[i].t - q[i - 1].t) continue;

            if(j + q[i].h >= h)
            {
                cout << q[i].t << endl;
                return 0;
            }


            f[cur][j + q[i].h] = max(f[pre][j] - (q[i].t - q[i - 1].t), f[cur][j + q[i].h]);//刷表法
            f[cur][j] = max(f[cur][j], f[pre][j] + q[i].v - (q[i].t - q[i - 1].t));

       }
        res = max(res, f[cur][0] + q[i].t);  
    }
    cout <<res << endl;
}

5.5 排兵布阵分组背包建模

题意

$\space\space\space\space\space$ 小明将总人数分为n组进入n组战场争夺每组争斗互不干涉每组争斗获胜会获得该战场相应的分数给定其余选手的战场人数分布问如何排兵布阵使得最后分数最高

分析

$\space\space\space\space\space$ 分组背包建模因为每个战场中的每场比赛决策相同所以在每个战场我们能获得该分数的个数只有其余玩家在该战场派兵人数小于主角的个数所以我们将问题转化对玩家的出场人数进行排序进行分组背包01决策决策的代价是每名玩家的出场人数 + 1，而价值则是排序后第i个出场时的价值 i * wk

源码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 110, M = 2e4 +10;
int f[M];
int g[M][N],v[M], w[M];
int s, n, m;

int main()
{
    cin >> s >> n >> m;

    for(int i = 1; i <= s; i ++)
       for(int j = 1; j <= n; j ++)
           cin >> g[j][i];

    for(int i = 1; i <= n; i ++)
    {
        sort(g[i] + 1, g[i] + s + 1);
        for(int j = 1; j <= s; j ++)
          v[j] = 2 * g[i][j] + 1, w[j] = i * j; // 转化分组背包问题

        for(int j = m; j >= 0; j --)
          for(int k = 1; k <= s; k ++)
            if(j >= v[k]) f[j] = max(f[j], f[j - v[k]] + w[k]);
    }
    cout << f[m] << endl;

}

5.6 Cow Exhibition G 背包问题建模

题意

$\space\space\space\space\space$ 每个奶牛均有智商和情商划分我们对每头奶牛进行01决策使得在满足智商之和大于0 情商之和也大于0下的智商和情商最大值

分析

$\space\space\space\space\space$ 本题是对每头牛进行01决策属于01背包问题我们同样需要判断j最优表示什么我们发现本题可以作为状态的有智商情商智商+情商因为我们最后要判断的是智商+情商并且将j代表智商情商之和话无法满足前者两项的前提所以我们的j要么代表智商或者情商那么难道我们需要开三维来用一维计量智商情商和吗？不需要本题的智商+情商跟智商情商练习很大我们完全可以在后期枚举选取那么我们的j可以代表智商而f[]代表情商最后循环求解最值和即可

本题也是f[i]代表恰好为i的情况所以注意初始化

源码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
const int N = 1e6 + 10, M = 400 * 1000;

struct Node
{
    int x, y;
}q[N];
int n, ans;
int f[N];

int main()
{

    cin >> n;
    for(int i = 1; i <= n; i ++)  cin >> q[i].x >> q[i].y; 

    memset(f, -0x3f, sizeof f);
    f[M] = 0;

    for(int i = 1; i <= n; i ++)
    {
        if(q[i].x >= 0)
        {
            for(int j = 2 * M; j >= q[i].x; j --)
                f[j] = max(f[j], f[j - q[i].x] + q[i].y);
        }
        else
        {
            for(int j = 0; j <= q[i].x + 2 * M; j ++)
               f[j] = max(f[j], f[j - q[i].x] + q[i].y);
        }
    }

    for(int i = M; i <= M + M; i ++)
    {
        if(f[i] > 0)
          ans = max(ans, f[i] + i - M);
    }
    cout << ans << endl;

}

5.7 飞扬的小鸟背包建模 01背包 + 完全背包

题意

$\space\space\space\space\space$ 从任意一个合法的高度出发每一步可以多次上升或一次下降在不碰撞到上下管道的情况下如果成功抵达另一端输出最少的点击次数反之输出通过的管道

分析

$\space\space\space\space\space$ 需要注意的是上升是可以连续多次上升也即是完全背包问题而下降则是仅一次是01背包问题那么我们定义f[i][j]为前i个物品在高度为j的最少点击数故此初始化我们赋值为最值(因为开始的位置高度可以随意所以我们f[0][i] = 0) 然后枚举所有管道每一个管道进行高度枚举进行背包决策需要注意的是我们的高度有上限所有在j >= m的时候需要额外分析

源码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e4 + 10, M = 1010, INF = 1e9;

int up[N], down[N], d[N], q[N];
int f[N][M];
int n, m, k, p, l, h;
void mem()
{
    for(int i = 0; i <= n; i ++)
      for(int j = 0; j <= m; j ++)
      {
          if(i == 0 && j != 0) continue;
          else f[i][j] = INF;
      }     
}

void get_move()
{
    for(int i = 1; i <= n; i ++)
    {
        //上升情况
        for(int j = 1; j <= m; j ++) // 不能枚举管子的高度来进行枚举 因为此处是完全背包 我们不知道选了几次 枚举实际可行高度无法叠加选举次数
        {
            if(j >= up[i - 1])
            {
                f[i][j] = min(f[i][j], f[i - 1][j - up[i - 1]] + 1);
                f[i][j] = min(f[i][j], f[i][j - up[i - 1]] + 1);
            }
            if(j == m)
            {
                for(int k = m - up[i - 1]; k <= m; k ++)
                {
                    f[i][j] = min(f[i][j], f[i - 1][k] + 1);
                    f[i][j] = min(f[i][j], f[i][k] + 1);
                }
            }
        }    
        //下降 枚举
        for(int j = d[i] + 1; j <= q[i] - 1; j ++)
            if(j + down[i - 1] <= m)   f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]);

               //有水管的地方置为INF    
        for(int j = 1; j <= d[i]; j ++) f[i][j] = INF;
        for(int j = q[i]; j <= m; j ++) f[i][j] = INF;        
    }

}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < n; i ++) cin >> up[i] >> down[i];

    for(int i = 1; i <= n; i ++) d[i] = 0, q[i] = m + 1;
    for(int i = 1; i <= k; i ++)
    {
        cin >> p >> l >> h;
        d[p] = l, q[p] = h;
    }

    mem();
    get_move();

    int cnt = k, ans = INF;
    for(int i = n; i >= 1; i --)
    {
        for(int j = d[i] + 1; j <= q[i] - 1; j ++)  ans = min(ans, f[i][j]);

        if(ans != INF) break;
        if(q[i] <= m) cnt --;
    }

    if(cnt == k) cout << 1 << endl << ans << endl;
    else cout << 0 <<endl << cnt << endl;
}