历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 734. 能量石【01背包 + 贪心（邻项交换）】原题链接困难

作者：

一只野生彩色铅笔 , 2021-06-28 22:11:32 , 所有人可见 , 阅读 3710

53

11

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

共有 $N$ 块魔法石

每块魔法石,吃掉的时间是 $s_i$,价值是 $w_i$,每单位时间内损失的能量是 $l_i$

规定，每块魔法石刚开吃的时候就会立刻获得他的价值（不会在吃的过程中损失能量）

每块魔法石一旦开吃就不能停下,魔法石能量损失到 $0$ 以后不会额外损失

求借一种方案，使得最终获得的 总价值 最大

分析

本题抛开 魔法石会损失能量 的限制，就是一道 01背包 的裸题

但是以往的 01背包 每个物品的价值是不变的，因此我们可以指定任意的次序进行 线性dp 求解

但是本题有 魔法石会损失能量 这一限制

因此 如何枚举物品的次序 是首要解决的问题，然后才可以套用 01背包模型 求解

我们这里采用 贪心思路 ，从分析 贪心解 中两个 相邻物品 的次序来入手

假设在 贪心解 中存在 $stone_i, stone_j$ 满足 $j = i + 1$ 且枚举到 $stone_j$ 时，能量都不为 $0$

如果能量为 $0$ ，那么他们的次序可以任意安排

则存在如下不等式（次序 $\overline{\mathrm{x~x~}i~j\mathrm{~x~x}}$ 获得的价值 大于等于 $\overline{\mathrm{x~x~}j~i\mathrm{~x~x}}$ 获得的价值）
$$ E_i + E_j - S_i \times L_j \ge E_j + E_i - S_j \times L_i \\\ S_j \times L_i \ge S_i\times L_j $$
于是对于最优解中所有 $S_j \times L_i \lt S_i\times L_j$ 的物品次序，我们都可以通过一次 邻项交换 的操作变成我们上述的次序，且保证该次交换完成后，总价值不减少

于是得以证明出 贪心解 $\ge$ 最优解

而由于 贪心解 本就是 合法解 ，因此自然而然 贪心解 $\le$ 最优解

得证：贪心解 $=$ 最优解

于是我们可以直接用 结构体 存储每个物品的三个属性，接着按照上述的次序 从小到大排序

就会获得能够达到 最优解 的物品次序，然后就是经典 01背包线性DP 求 最大价值 问题

闫氏DP分析法

$f(i, j)$— 状态表示（集合）：考虑前 i 个魔法石，且吃掉最后一个魔法石后，所用总时间恰好为 j 的方案

$f(i, j)$— 状态表示（属性）：方案的总价值 最大 MAX

$f(i, j)$ — 状态计算：

吃掉第 i 个魔法石 — $f(i - 1,j - s_i) + e_i - (j-s_i)\times l_i$
不吃第 i 个魔法石 — $f(i-1, j)$

Code

时间复杂度： $O(N \times \sum s_i)$

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

using namespace std;

const int N = 110, M = 1e5 + 10;

int n, m;
struct Node
{
    int s, e, l;
    bool operator< (const Node& t) const
    {
        return s * t.l < t.s * l;
    }
}a[N];
int f[M];

void solve()
{
    //求恰好的背包DP,为了保证状态都是从起点转移的,要把非起点初始化为无穷大以避免转移
    memset(f, -0x3f, sizeof f);
    f[0] = m = 0;
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i].s >> a[i].e >> a[i].l, m += a[i].s;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = m; j >= a[i].s; -- j)
        {
            int pre = j - a[i].s;
            f[j] = max(f[j], f[pre] + a[i].e - pre * a[i].l);
        }
    }
    int res = 0;
    for (int j = 0; j <= m; ++ j) res = max(res, f[j]);
    cout << res << endl;
}
int main()
{
    int T = 1, t = 1;
    cin >> T;
    while (T -- )
    {
        cout << "Case #" << t ++ << ": ";
        solve();
    }
    return 0;
}

33 评论

残阳如血 9个月前

为什么这样错了？

#include <cstring>
#include <iostream>
#include <algorithm>
const int MAXN = 1e2 + 10, MAXV = 1e4 + 10;

int T, N, V, f[MAXV];

struct stone {
  int s, e, l;
  bool operator<(const stone &sto) const {
    return s * sto.l < sto.e * l;
  }
} st[MAXN];

int main() {
  std::cin >> T;
  for (int test = 1; test <= T; ++test) {
    std::cin >> N, f[0] = V = 0;
    for (int i = 1; i <= N; ++i) std::cin >> st[i].s >> st[i].e >> st[i].l, V += st[i].s;
    std::sort(st + 1, st + N + 1);
    for (int i = 1; i <= N; ++i) {
      for (int j = V; j >= st[i].s; --j) {
        f[j] = std::max(f[j], f[j - st[i].s] + std::max(0, st[i].e - (j - st[i].s) * st[i].l));
      }
    }
    std::cout << "Case #" << test << ": " << f[V] << std::endl;
  }
  return 0;
}

残阳如血 9个月前

已经找出了一个错误，重定义里面改为 s * sto.l < sto.s * l，但是还是错误/kk

picapika 2022-09-17 23:11

为什么yls的代码不用memset而这里要用呢

还没想好要取什么id 2022-11-17 10:51

y总的是二维没优化

铃兰の顶点 2021-09-20 20:33

“如果能量为0，那么他们的次序可以任意安排” 这句话要咋理解呀

一只野生彩色铅笔 2021-09-20 20:42

吸收一个能量石需要时间，所以初始时，能量石的次序会影响物品的价值

但是如果吸收完前 $i$ 个能量石后，剩下的 $n-i$ 个能量石的剩余能量为 $0$

则他们的次序，就不会影响最终的方案了（怎么放都是 $0$

铃兰の顶点 2021-09-20 21:03 回复了一只野生彩色铅笔的评论

就是dp的时候碰到那种变成零的石头会在dp中隐式地不取它是吗

一只野生彩色铅笔 2021-09-20 21:07 回复了铃兰の顶点的评论

不是不取他，这里还没到dp部分，还在贪心排序的部分

证明如果为0，次序可以任意安排，是为了证明我们的这种排序方法也可以是最优解

铃兰の顶点 2021-09-20 21:17 回复了一只野生彩色铅笔的评论

终于懂了！太感谢了！这题我想了好久

铃兰の顶点 2021-09-20 21:55 回复了一只野生彩色铅笔的评论

大佬不好意思我想再问一个小问题
假如我们对一堆石子进行操作时可以保证n个中的x个能量不降低成0 不过吃的该顺序没有按照s/l最小进行排序假定这x个石子中的第i个和第i+1个不满足s/l从小到大的顺序并且我们在对i和i+1进行交换的时候发现原先第i个石子的能量降低成0了对于该情况该怎么办

一只野生彩色铅笔 2021-09-20 22:14 回复了铃兰の顶点的评论

$$ E_i + E_j - S_i \times L_j \ge E_j + E_i - S_j \times L_i $$

根据你上述情形，不等式左侧 $E_j - S_i \times L_j < 0$

而不等式左侧实际应该是 $E_i + 0$，却因为我们上述排序加了一个负数，我们设为 $k(\ge 0)$

既然 $E_i - k \ge E_j + E_i - S_j \times L_i$

则必然 $E_i \ge E_j + E_i - S_j \times L_i$，对于上述排序依然有效～

铃兰の顶点 2021-09-20 22:33 回复了一只野生彩色铅笔的评论

好的~谢谢！

baikun 8个月前

怎么判断f[i,j]是表示价值恰好为j 还是价值不超过j

yelanyanyu 2023-07-09 21:35

有点不理解。照理来讲，背包问题其实本质是选择出一个最优的子序列。难道不会存在这样的一个情况：当我们交换之后，子序列的选法也会发生变化（由于有时间消耗，导致原序列也会发生改变，做最优决策的时候就会导致各个物品的选法不同）。也就是说交换邻项的操作实际上是会影响其他位置的决策的。
所以，这个证明我感觉有一些问题。或者说，是我哪里欠考虑了。

零分下一个 2023-07-26 22:14

确实，我也是这样想的，就是因为我们吃某一块能量石时，所有没吃过的能量石都会损失能量，所以我想的办法时尽量让损失的能量变少，假设没有能量损失的话，我们的总能量无疑就是所有能量的总和，而现在有了能量损失，为了获得尽可能多的能量，我们要想办法减少能量损耗，所以我们不妨只考虑没有吃过的能量块，现在要从中选择第i块来吃，那么我们吃完后剩余的能量为E-Ei-Si(所有石头L总和-之前选过的石头L总和)+SiLi,其中E为选择时剩余能量石能量的总和，Ei，Si，Li均是针对选择的能量石而言，本着贪心的原则，我们应该选择Ei+Si(所有石头L总和-之前选过的石头L总和)-SiLi最小的那一块石头，然后就没有然后了，就卡住了hh~

Zcras 2023-10-16 13:30

有没有一种可能，任意两项按照相对顺序选取就是最优解，具体可以看贪心式子，这个sort相当于把整个数组都按照这个键值排序了，所以优先考虑靠前的是必然不会导致答案变差的

醒了不起的盖兹比 2023-04-26 19:55

励志走遍每一个彩铅哥的每一个题解

梦想彼方 2022-07-13 13:38

   for (int j = m; j >= a[i].s; -- j)
        {
            int pre = j - a[i].s;
            f[j] = max(f[j], f[pre] + a[i].e - pre * a[i].l);
        }

彩铅巨巨，这里为什么不用写f[pre] + max(0,a[i].e - pre * a[i].l)呢

卡路西法 2022-09-15 22:20

因为两者是等效的，这里分类讨论：
1.取max：如果后面石头还有能量剩余，那么意味着此时吃这个石头我不仅不会得到收益，还会影响我后面石头的收益（吃当前石头会耗费时间，使后面石头能量减少），所以此时就不会吃当前石头了；而如果后面石头剩余能量已经都为零了，那此时取max就意味着我吃了当前石头但当前石头收益为0，不影响答案；
2.不取max:意味着我吃了当前石头非但每收益，还会有损益，那么无论什么情况我都不会吃当前石头了
总结：两者对应实际含义不同，但在本题中结果是相同的。拓展一下，如果给定最大吃能量石时间问吃到最多能量的情况下最多能吃多少石头那么就必须取max了

啥也不会hh 2022-03-18 15:20

是不是含在口中的能量不会随时间逐渐递减啊？？？

辰chen 2022-03-24 16:41

是的

leimingze 2022-02-20 16:00

这题为什么不能用不超过来实现呢，如果用不超过来实现，最后是不是就不用枚举res了

一只野生彩色铅笔 2022-02-24 07:53

都可以，用“恰好的”来定义的话，对于这题的理解思维度较小

如果用“不超过”来定义的话，还用到了一个贪心思路，如果当前未处于进食状态，就必定会尽可能去选择石头进行食用

对于本题来说都可

leimingze 2022-02-24 08:02 回复了一只野生彩色铅笔的评论

%%%%大佬请问如果用不超过这题怎么写

椒盐土豆 2022-02-24 20:56 回复了 leimingze 的评论

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int f[110][N],n,m,t,cnt,res;
struct stone{
    int s, e, l;
    bool operator<(const stone &k )const{
        return s * k.l < k.s * l;
    }
}a[N];
int main(){
    cin>>t;
    while( t >= ++cnt ){
        cin>>n;
        m=0;    //能量视为体积
        res=0;  //记录最大值
        memset(f, 0, sizeof f);
        // memset(f, -0x3f, sizeof f);//求恰好达到能量最大值前初始化
        // f[0]=0; 
        for (int i = 1; i <= n; i ++ ){
            cin>>a[i].s>>a[i].e>>a[i].l;
            m+=a[i].s;
        }
        sort(a+1, a+n+1);                           // e1+e2-s1*l2 < e1+e2-s2*l1
        for (int i = 1; i <= n; i ++ ){
            int l = a[i].l , s = a[i].s , e = a[i].e ;
            for (int j = 0; j <= m; j ++ ){
                if( j >= s )f[i][j] = max( f[i-1][j] , f[i-1][j-s] + max(0,e-(j-s)*l));
                else f[i][j]=f[i-1][j];
                res = max(res , f[i][j]);
            }
        }
        cout<<"Case #"<<cnt<<": "<<res<<endl;
    }
}