优化成一维后 从后往前 遍历

装箱问题

思路: 把体积当作价值跑一遍01背包

宠物小精灵之收服

模型: 二维费用 + 01背包

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

using namespace std;

const int N = 1010, M = 505;

int n, V1, V2;
int f[N][M];

int main()
{
    cin >> V1 >> V2 >> n;

    for (int i = 1; i <= n; i ++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        for (int j = V1; j >= v1; j --)
            for (int k = V2 - 1; k >= v2; k --)
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }

    cout << f[V1][V2 - 1] << ' ';

    int k = V2 - 1;

    while (k && f[V1][k - 1] == f[V1][V2 - 1]) k --;
    cout << V2 - k;
    return 0;
}

潜水员

模型: 二维费用 + 01背包

注意:本题的$f[i][j]$表示氧气大于等于$i$, 氮气大于等于$j$的最小费用

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

using namespace std;

const int N = 22, M = 80;

int V1, V2;
int n;
int f[N][M];

int main()
{
    cin >> V1 >> V2 >> n;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;

        for (int j = V1; j >= 0; j --)
            for (int k = V2; k >= 0; k --)
                f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
    }

    cout << f[V1][V2];
    return 0;
}

能量石

贪心 + $01$背包

考虑第$i$个能量石和第$i + 1$个能量石:

• 若先吃第$i$个,则收益为$w_i = e_i + e_{i+1} - s_i * l_{i + 1}$;

• 若先吃第$i + 1$个,则收益为$w_{i + 1} = e_i + e_{i + 1} - s_{i + 1} * l_i$;

若$w_i > w_{i + 1}$, 则 $s_i * l_{i + 1} < s_{i + 1} * l_i$, 即$ \frac {s_i}{l_i} < \frac {s_{i + 1}}{l_{i + 1}}$

因此我们只需要按照$\frac {s_i}{l_i}$的值从小到大排序, 然后再做一遍$01$背包

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

using namespace std;

const int N = 110;

struct Stone
{
    int s, e, l;
    bool operator < (Stone const & S) const
    {
        return s * S.l < S.s * l;
    }
}a[N];

int T, n;
int f[N * N];

int main()
{
    scanf ("%d", &T);

    for (int t = 1; t <= T; t ++)
    {
        scanf ("%d", &n);
        int m = 0;
        for (int i = 0; i < n; i ++)
        {
            int s, e, l;
            scanf ("%d %d %d", &s, &e, &l);
            a[i] = {s, e, l};
            m += s;
            // m表示吃完所有能量石的总时间->总体积
        }

        sort(a, a + n);
        // 集合表示的是体积恰好为j时的最大价值(这样做的目的是为了防止下面e - (j - s) * l小于0对答案造成影响)
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        for (int i = 0; i < n; i ++)
        {
            int s = a[i].s, e = a[i].e, l = a[i].l;
            for (int j = m; j >= s; j --)
                f[j] = max(f[j], f[j - s] + e - (j - s) * l); // 表示的是在j时刻吃能量石
                // j - s表示的是在全局时间上吃能量石时该能量石还剩的价值
        }

        int res = 0;
        for (int i = 0; i <= m; i ++) res = max(res, f[i]);
        printf ("Case #%d: %d\n", t, res);
    }
    return 0;
}