算法提高课第一章背包模型

多种多样的背包问题

采药

01背包

装箱问题

01背包

AcWing 1022. 宠物小精灵之收服

多重背包，一题三解。
有一些精灵球，皮卡丘有一定的体力，在保证收服尽可能多的小精灵的情况下，使得皮卡丘的体力剩余最多

• 皮卡丘的体力必须大于1，不然就裂开
• 首先多收服小精灵，其次是少消耗体力

多价值评价

很容易想到，小精灵的价值大，体力的价值小，而且消耗体力是减少价值。这样题目就变成了裸的多重背包

根据题目范围：可以设定小精灵的价值为10000，消耗体力的价值为-1，这要求得的最大价值就是一个混合体，解开就得到了最多小精灵和最小消耗体力

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

using namespace std;
const int N = 1010;
int n, m, k;
int a[110], b[110];
int dp[1010][510];
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++ )
    {
        cin >> a[i] >> b[i];
    }
    //重新定义权值，1个小精灵10000分，消耗1点体力-1分
    for(int i = 1; i <= k; i ++ )
    {
        for(int j = n; j >= a[i]; j -- )//对dp进行一维压缩才能这么写，不然j和p要到0结束才行。
        {
            for(int p = m; p >= b[i] + 1; p --)
            {
                dp[j][p] = max(dp[j][p], dp[j - a[i]][p - b[i]] + 10000 - b[i]);
            }
        }
    }
    int q = dp[n][m];
    if(!q) cout << "0 " << m << endl;
    else
	cout << (q + 9999) / 10000 << " " << m - (10000 - (q % 10000));
}

求特解（恰好的解）

dp可以求恰好装满j体积的最大价值

我们可以求恰好满足最多小精灵的所有特定体力和精灵球，找到精灵最多的体力最大的解即可。

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

using namespace std;
const int N = 1010;
int n, m, k;
int a[110], b[110];
int dp[1010][510];
const int inf = 1e9;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++ )
        cin >> a[i] >> b[i];
    //另一个思路，考虑恰好成功的情况，这样可以记录答案，不过要先初始化
    for(int i = 1; i <= k; i ++ )
    for(int j = 0; j <= n; j ++ )
    for(int p = 0; p <= m; p ++ )
        dp[j][p] = -inf;
    int ans = 0, tl = inf;
    dp[0][1] = 0;//有0个精灵球，皮卡丘体力为1时可以捕获0个精灵。
    for(int i = 1; i <= k; i ++ )
    {
        for(int j = n; j >= a[i]; j -- )//对dp进行一维压缩才能这么写，不然j和p要到0结束才行。
        {
            for(int p = m; p >= b[i] + 1; p --)
            {
                dp[j][p] = max(dp[j][p], dp[j - a[i]][p - b[i]] + 1);
                if(dp[j][p] >= ans)
                {
                    if(ans == dp[j][p])
                    tl = min(tl, p);
                    else tl = p;
                    ans = dp[j][p];
                }
            }
        }
    }
    if(!ans) cout << 0 << ' ' << m;
    else cout << ans << ' ' << m - tl + 1;
}

等价dp

在背包问题中，体积w与价值v是可以互逆的！
可以将$f[i]$表示为体积为$i$能装的最大价值，
也可以将$f[i]$]表示为价值为$i$所需的最小体积。
两者等价，我们只需要选择范围较小的那维作为体积就可以了！
这直接影响到时空复杂度。
这题就是个案例。

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

const int N = 1005, M = 505, S = 105;
const int inf = 0x3f3f3f3f;
int n, m, K, dp[M][S];
//f[i][j] 表示体力为i，收集了j个精灵用的最小的精灵球数量
int main()
{
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> m >> K;
    dp[0][0] = 0;
    for(int i = 1, c, d; i <= K; i ++ )
    {
        cin >> c >> d;
        for(int j = m; j >= d; j -- )
        for(int k = K; k >= 1; k -- )
            if(dp[j - d][k - 1] + c <= n)
                dp[j][k] = min(dp[j][k], dp[j - d][k - 1] + c);
    }
    for(int k = K; k >= 0; k -- )
    {
        int p = inf;
        for(int j = 0; j < m; j ++ )
        if(dp[j][k] != inf && j < p)
        {
            p = j;
        }
        if(p != inf)
        {
            printf("%d %d\n", k, m - p);
            return 0;
        }
    }
}

278. 数字组合

恰好有解的方案数
只需要把dp[0]设置为1即可

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

using namespace std;
int dp[10001];
int a[110];
int n, m;
int main()
{
    //恰好为M
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    dp[0] = 1;
    for(int i = 1; i <= n; i ++ )
    for(int j = m; j >= a[i]; j -- )
    {
       dp[j] += max(0, dp[j - a[i]]);
    }
    cout << dp[m];
}

货币系统2

要求找到最简的等价的货币系统
容易想到，最小的币值是不能变的，大一点的币值如果可以被小的币值表示，那么也就可以省略

可以对币值进行排序，不断的求解方案数。如果当前币值得方案是已经存在的，那么$ans-1$

#include <iostream>
#include <cstring>
#include <algorithm>
//3 10
using namespace std;
bool dp[25010];
int a[200];
int n;
int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        cin >> n;
        int ma = 0;
        for(int i = 1; i <= n; i ++ ) 
        {
            cin >> a[i];
            ma = max(ma, a[i]);
        }
        sort(a + 1, a + 1 + n);
        memset(dp, 0, sizeof dp);
        //5 10 100
        int ans = n;
        dp[0] = true;
        //一个大的数如果可以用一些小的数表示，那么肯定要小的数
        for(int i = 1; i <= n; i ++ )
        {
            if(dp[a[i]])
            {
                ans --;
                continue;
            }
            for(int j = a[i]; j <= ma; j ++ )
                dp[j] |= dp[j - a[i]];
        }
        cout << ans << endl;
    }
}

庆功会

注意选择策略放最后

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

using namespace std;
int n, m;
const int N = 510;
const int M = 6100;
int v[N], w[N], s[N];
int dp[M];
int main()
{
    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 k = m; k >= 0; k -- )
        for(int j = 1; j <= s[i]; j ++ )//策略放最后
        {
            if(k - j * v[i] < 0) break;
            dp[k] = max(dp[k], dp[k - j * v[i]] + j * w[i]);   
        }
    }
    cout << dp[m];
}

1020. 潜水员

满足条件的最小重量
可以求特解，不过可能特解的氧气和氮气特别大
改进一下，定义$dp[j][p]$为氧气至少$j$，氮气至少$p$的最小重量。这样$j$、$p$可以更新到0
$$dp[j][p]=min(dp[j][p],dp[max(0,j-a[i])][max(0,p-b[i])]+c[i])$$

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

using namespace std;
const int N = 1100;
int m, n, k;
int a[N], b[N], c[N];
int dp[30][80];
int main()
{
    cin >> m >> n;
    cin >> k;
    for(int i = 1; i <= k; i ++ ) cin >> a[i] >> b[i] >> c[i];
    //定义dp[j][p]为j个氧气p个氮气的最小重量
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= k; i ++ )
    for(int j = m; j >= 0; j -- )
    for(int p = n; p >= 0; p -- )
        dp[j][p] = min(dp[j][p], dp[max(0, j - a[i])][max(0, p - b[i])] + c[i]);
    cout << dp[m][n];
}

机器分配

多重背包/分组背包的具体方案
学习一下这种输出方式，记录每个物品每个体积下的最优选择。

#include<stdio.h>
#define N 20
int f[N], w[N], g[N][N];

void print(int x, int y)
{
    if(x == 0)  return;

    int k = g[x][y];
    print(x - 1, y - k);
    printf("%d %d\n", x, k);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)  scanf("%d", &w[j]);

        for(int j = m; j; j --)
            for(int k = 1; k <= j; k ++)
            {
                int val = f[j - k] + w[k];
                if(val > f[j])
                {
                    f[j] = val;
                    g[i][j] = k;
                }
            }
    }

    printf("%d\n", f[m]);
    print(n, m);
    return 0;
}

734. 能量石

题解

非常特殊的背包问题
根据某种特殊规则得到最大价值，这类问题的特征是选择物品的次序影响结果，所以要想办法根据某些属性确定最佳答案的物品次序。对物品进行排序后转化为01背包，要这个物品或者不要。

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

using namespace std;
const int N = 105;
const int M = 10005;
int n;
int dp[M];
struct node
{
    int s, e, l;
}a[N];
bool cmp(node p, node q)
{
    return p.s * q.l <= q.s * p.l;
}
int main()
{
    int t;
    cin >> t;
    
    for(int p = 1; p <= t; p ++)
    {
        memset(dp, 0xcf, sizeof dp);
        cin >> n;
        dp[0] = 0;
        int tmp = 0;
        for(int i = 1, s, e, l; i <= n; i ++ )
        {
            cin >> s >> e >> l;
            tmp += s; a[i] = (node){s, e, l};
        }
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1; i <= n; i ++ )
        for(int j = tmp; j >= a[i].s; j -- )
        {
            dp[j] = max(dp[j], dp[j - a[i].s] + max(0, a[i].e - (j - a[i].s) * a[i].l));
        }
        int res = 0;
        for(int i = 1; i <= tmp; i ++ ) res = max(res, dp[i]);
        printf("Case #%d: %d\n", p, res);
    }
}

638. 大礼包 - 力扣（LeetCode）

复杂背包问题，可以使用记忆化搜索解决

class Solution {
public:
    map<vector<int>, int> mp;
    //记忆化搜索 满足需求的最小价格，使用map存储
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int n = price.size();
        return dfs(price, needs, special, n);
    }
    // 记忆化搜索计算满足购物清单所需花费的最低价格
    int dfs(vector<int> price, vector<int> curNeeds, vector<vector<int>> & special, int n) {
        if (!mp.count(curNeeds)) {
            int minPrice = 0;
            for (int i = 0; i < n; ++i) {
                minPrice += curNeeds[i] * price[i]; // 不购买任何大礼包，原价购买购物清单中的所有物品
            }
            for (auto & x : special) {
                int specialPrice = x[n];
                vector<int> nxtNeeds;
                for (int i = 0; i < n; ++i) {
                    if (x[i] > curNeeds[i]) { // 不能购买超出购物清单指定数量的物品
                        break;
                    }
                    nxtNeeds.emplace_back(curNeeds[i] - x[i]);
                }
                if (nxtNeeds.size() == n) { // 大礼包可以购买
                    minPrice = min(minPrice, dfs(price, nxtNeeds, special, n) + specialPrice);
                }
            }
            mp[curNeeds] = minPrice;
        }
        return mp[curNeeds];
    }
};

1449. 数位成本和为目标值的最大数字 - 力扣（LeetCode）

class Solution {
public:
    //恰好target
    //成本cost
    //价值为 i + 1,而且不断增加
    //一个思路是先找到能够实现的最高位数, 然后找到这个位数的最佳方案
    int f[5500];
    string largestNumber(vector<int>& cost, int target) {
        memset(f, 0xcf, sizeof(f));
        f[0] = 0;
        for(int i = 1; i <= 9; i ++ )
        {
            for(int j = cost[i - 1]; j <= target; j ++)
            {
                f[j] = max(f[j], f[j - cost[i - 1]] + 1);//每个的价值都是1
            }
        }
        string ans = "";
        int w = target;
        for(int i = 1; i <= f[target]; i ++ )//每位都选一个数的最大值
        {
            for(int k = 9; k >= 1; k -- )//从大向小选
            {
                
                if(w - cost[k - 1] >= 0 && f[w] == f[w - cost[k - 1]] + 1)//选完这个数之后最多位数减1，则这一位选择这个         
                {
                    w -= cost[k - 1];
                    ans += (char)(k + '0');
                    break;
                }
            }
        }
        if(ans == "") return "0";
        return ans;
    }
};

879. 盈利计划 - 力扣（LeetCode）

简单思路

找到恰好为$i$价值$j$人数的方案数，然后加起来

class Solution {
public:
    //n名员工，选择一些工作，求出满足最小利润的方案
    //f[N][N] 价值N, 体积N的方案数
    int f[10010][110];
    const int p = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int sum = 0;
        for(auto x: profit) sum += x;
        f[0][0] = 1;//恰好的方案只在f[0][0] 初始化
        for(int i = 0; i < group.size(); i ++ )
        for(int j = sum; j >= profit[i]; j -- )//枚举所有利润
        for(int k = n; k >= group[i]; k -- )
        {
            f[j][k] += f[j - profit[i]][k - group[i]];
            f[j][k] %= p;
        }
        int ans = 0;
        for(int i = 0; i <= n; i ++ )
        for(int j = minProfit; j <= sum; j ++ )
        {
            ans += f[j][i];
            ans %= p;
        }
        return ans;
    }
};

利润至少

利润至少，那么利润至少1可以从利润至少0转移过来

class Solution {
public:
    //n名员工，选择一些工作，求出满足最小利润的方案
    //价值和容量可以互换
    //f[N][N] 价值N, 体积N的方案数
    int f[110][110];
    const int p = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        f[0][0] = 1;
        for(int i = 0; i < group.size(); i ++ )
        for(int j = minProfit; j >= 0; j -- )
        for(int k = n; k >= group[i]; k -- )
        {
            f[j][k] += f[max(0, j - profit[i])][k - group[i]];
            f[j][k] %= p;
        }
        int ans = 0;
        for(int i = 0; i <= n; i ++ ) 
        {
            ans += f[minProfit][i];
            ans %= p;
        }
        return ans;
    }
};

至少至多

设定状态$f[i][j]$ 表示至少$i$价值，至多$j$人的方案数

class Solution {
public:
    //三种思路之间的区别。
    int f[110][110];
    const int p = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int sum = 0;
        for(auto x: profit) sum += x;
        for(int i = 0; i <= n; i ++ )//至多i人，价值为0的方案初始化为1
            f[0][i] = 1;
        for(int i = 0; i < group.size(); i ++ )
        for(int j = minProfit; j >= 0; j -- )
        for(int k = n; k >= group[i]; k -- )
        {
            f[j][k] += f[max(0, j - profit[i])][k - group[i]];//至少价值j，则多于价值j的方案也要加入，如至少价值1，那么利润2的方案可以加入，也就是说j可以从至少价值为0的方案转移过来。
            f[j][k] %= p;
        }
        return f[minProfit][n];
    }
};