POJ - 2184 Cow Exhibition 题解
2024-10-09 07:21:07
题目大意
有 \(N(N \le 100)\) 头奶牛,没有头奶牛有两个属性 \(s_i\) 和 \(f_i\),两个范围均为 \([-1000, 1000]\)。
从中挑选若干头牛,\(TS = \sum s[choose], TF = \sum f[choose]\)。
求在保证 \(TS\) 和 \(TF\) 均为非负数的前提下,\(TS+TF\)最大值。
样例
有 5 头牛,下面分别是每头牛的两个属性
5
-5 7
8 -6
6 -3
2 1
-8 -5
选择第 1、3、4 三头牛为最优解
虽然加上 2 号,总和会更大,但是 TF 会变成负数,不合法
分析
- 首先从问题入手,先搞特殊情况:如果两个属性均为负数,果断舍弃,因为它一直在做负贡献
- 一个物品有两个属性,会很自然想到二维费用背包,每个物品的价值为两个属性的和,也就是两种费用的和,这样定义其实意义并不大,而且时间复杂度为 \(O(N*S*F)\),最大会到 \(10^8\),应该会超时。
- 由于价值直接是两者的和,所以我们没必要单独构造一个价值,而是把其中的一维改成价值即可,即用 \(S_i\) 当作费用,\(F_i\) 当作价值,最后扫一遍求最大和就可以了
- 另外一个棘手的问题就是负数的问题:
- 对于价值来说,正负都不影响,直接正常跑背包求最大值即可
- 当费用为非负数时,没什么影响,正常跑 01 背包求最值,背包容积倒叙处理即可,\(f[j] = max \{f[j], f[j-s_i]+f_i\}\)。
- 当费用为负数时,如果直接用上述的式子,\(j-S_i > j\),而背包容积倒叙的话,\(f[j-s_i]\) 会先于 \(f[j]\) 被计算。如果直接这样写,会变成完全背包的样子,不妥。因此只需要把容积改成正序循环即可。
- 由于下标不能为负数,我们可以将 \(0\) 点改成 \(100*1000\),这样的话,即使所有物品的费用都为负数,下标也依旧处在合法的范围内。此时背包的容积也就相应变成了 \([0~200000]\)。
- 注意跑背包的时候的边界即可
- 最后统计时,当费用不小于 \(100000\) 时才表示 \(TS\) 的和为非负数,找到所有价值为非负数的那些,最后求两者和的最大值即可。
部分代码
心情好的时候再加
最新文章
- Sunny-Code Beta版总结会议
- 【简易版】Java ArrayList(增删改查)
- C#的TreeView标记
- Android NDK中的C++调试踩坑标记
- 基于Linux的oracle数据库管理 part6 (backup 相关的脚本)
- C++-bool的值
- pjsip视频通信开发(上层应用)之拨号键盘下部份拨号和删除功能
- HDU 1498 50 years, 50 colors (行列匹配+最小顶点覆盖)
- python描述符descriptor(一)
- JDK的下载和安装
- 提取HTML的正文类
- Android应用开发-小巫CSDN博客clientJsoup篇
- js 鼠标事件
- 采访 Lua 发明人的一篇文章
- 将文件转成clob添加到Oracle数据库中
- file /usr/share/mysql/charsets/README from install of MySQL-server-5.1.73-1.glibc23.i386 conflicts with file from package mysql-libs-5.1.73-8.el6_8.i686
- MySQL连接缓慢,打开缓慢原因
- sdn的相关学习系列之一mininet的安装
- 黄聪:WordPress 启用HTTPS设置(转)
- git 分支 branch 操作