算法提高课汇总

算法思路

理解题意

在$01$背包的基础上, 每个物品的价值会随时间线性损失. 此时除了考虑选择物品的集合, 选择物品
的顺序也需要考虑. 即本题考虑两个问题:

• 选择物品的顺序—贪心

• 确定顺序后选择哪些物品—$DP$

贪心

考虑过程与耍杂技的牛 类似.

考虑任意选择顺序下某时刻选择的2个相邻物品$i$和$i + 1$(所有物品的$L$满足$L\gt 0$).此时两个物品剩余能量为$E_i’, E_{i+1}’$.

不考虑$L = 0$的物品, 因为选择该物品的选择顺序任意, 可认为是一般的$01$背包中的物品.
本题实现时将$L = 0$的物品放在了最前面.

• 先吃$i$所获得能量: $E_i’ + E_{i+1}’ - S_i\times L_{i+1}$

• 先吃$i+1$所获得能量: $E_i’ + E_{i+1}’ - S_{i+1}\times L_{i}$

假设先吃$i$所获得能量更大, 即$- S_i\times L_{i+1}\ge - S_{i+1}\times L_{i}$-->$S_i\times L_{i+1}\le S_{i+1}\times L_{i}$-->$S_i/L{i}\le S_{i+1}/ L_{i+1}$. 所以如果我们按$S/L$升序排序的顺序选择物品获得能量最大. 当然实现时没有用除的方式比较, 否则需要考虑$L = 0$的物品, 不能直接除, 而可以直接将其结果置为一个很大的数值.

• 贪心策略: 按物品$S/L$升序排序后的顺序选择物品.

$DP$

因为物品价值随着时间会损失, 所以不同于$01$背包问题, 最后状态所花时间并不是越多越好. 所以
这里的时间是恰好而不是不超过.

状态定义 $dp(i, j)$

• 集合: 从前$i$个能量石中选, 且吃完所有石头后时间恰好为$j$.(体积恰好为$j$)的所有选择方案

• 属性:Max价值

状态计算

$01$背包划分思路: 以第$i$个物品选/不选来划分.

• 不选: $dp(i - 1, j)$

• 选: 注意此时吃石头$i$的起始时间为$j - S_i$且物品价值最小为0, 所以石头$i$的能量为
  $max\lbrace 0, E_i - (j - S_i)\times L_i\rbrace$.

代码实现

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

using namespace std;

const int N = 110, M = 100 * 100 + 10;

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

int n, m;
int dp[M];

int main()
{
    int T;
    cin >> T;
    for( int k = 1; k <= T; k ++ )
    {
        cin >> n;
        m = 0;
        for( int i = 0; i < n; i ++ )
        {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s; 
        }

        sort(stone, stone + n);
        memset(dp, -0x3f, sizeof dp);
        dp[0] = 0; //恰好定义下的唯一合法初始状态

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

        int res = 0;
        for( int j = 0; j <= m; j ++ )  res = max( res, dp[j] );
        printf("Case #%d: %d\n", k, res);
    }

    return 0;
}