在背包问题中,体积w与价值v是可以互逆的!
可以将$f[i]$表示为体积为$i$能装的最大价值,
也可以将$f[i]$表示为价值为$i$所需的最小体积。
两者等价,我们只需要选择范围较小的那维作为体积就可以了!
这直接影响到时空复杂度。
这题就是个案例。
算法1
(体力、精灵球数为费用、精灵数为价值) $O(nmk)$
$f[i][j]$表示为体力为$i$,精灵球数为$j$所收集到的最大精灵。
时间复杂度
差不多是$5 * 10^7$的级别。
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005, M = 505, S = 105;
int n, m, K, w[S], v[S], f[N][M];
int main() {
memset(f, 0xcf, sizeof f);
scanf("%d%d%d", &n, &m, &K);
for(int i = 1; i <= K; i++)
scanf("%d%d", w + i, v + i);
f[0][0] = 0;
for(int i = 1; i <= K; i++) {
for(int j = n; j >= w[i]; j--)
for(int k = m; k >= v[i]; k--)
f[j][k] = max(f[j][k], f[j - w[i]][k - v[i]] + 1);
}
int res = -1, t;
for(int j = 0; j <= n; j++) {
for(int k = 0; k < m; k++) {
if(f[j][k] > res || (res == f[j][k] && k < t)) {
res = f[j][k], t = k;
}
}
}
printf("%d %d\n", res, m - t);
return 0;
}
算法2
发现$k$很小,于是就…
(体力、精灵数为费用,精灵球数为价值) $O(k^2m)$
$f[i][j]$ 表示体力为 $i$, 收集了 $j$个 精灵 用的最小的精灵球数量
时间复杂度
大概是$5 * 10 ^ 6$的级别。
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005, M = 505, S = 105;
const int INF = 0x3f3f3f3f;
int n, m, K, f[M][S];
/*
f[i][j] 表示体力为 i, 收集了 j 个精灵 用的最小的精灵球数量
*/
int main() {
memset(f, 0x3f, sizeof f);
scanf("%d%d%d", &n, &m, &K);
f[0][0] = 0;
for (int i = 1, c, d; i <= K; i++) {
scanf("%d%d", &c, &d);
for (int j = m; j >= d; j--)
for (int k = K; k >= 1; k--)
if(f[j - d][k - 1] + c <= n)
f[j][k] = min(f[j][k], f[j - d][k - 1] + c);
}
for (int k = K; ~k; k--) {
int p = INF;
for (int j = 0; j < m; j++) {
if(f[j][k] != INF && j < p)
p = j;
}
if(p != INF) { printf("%d %d\n", k, m - p); return 0; }
}
return 0;
}
运行效率
这题启示我们,要用灵活的思维去考虑问题$qwq$
后面两重循环为啥都是从后往前遍历呢?
这里可以看作最简单的01背包,题解是少了一层i,相当于01背包优化空间了,但是实际上更清楚的可以使用f【】【】【】来解释说明,计算下一层的时候需要上一层的元素,而每一层需要上一层的数据比i相对应位置较小的数字,但是实际这个题的空间没有那么多,优化后就可以过了和上面代码大差不大
你被y总关注了好像
有没有一种可能,墨大佬是y总第一批优秀学员中数一数二的风云人物,且曾在ACsaber中暴捶y总
怎么锤的,有视频吗
https://www.bilibili.com/video/BV1E7411F7bq/?spm_id_from=333.999.0.0
貌似在这个视频里,y总自己承认的
致远星
恐怖如斯
第三重循环把int k=K改成int k=i更好好像,要不然会计算一些非法状态。
你说得对
memset(f, 0xcf, sizeof f);
这句什么意思呢
负无穷
3q
这个题的数据加强了,有刚好用完体力的
orz orz
wk,太nb了,这种换维度的思想,wk
墨佬nb!
sto orz
j从i开始遍历能再凹一点
tql,是我这猪脑想不出的了
大佬,这个条件你是怎么保证的
当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
如果此时他的体力正好等于该宠物的值,不是不能收服吗???
体力减一就行了
状态转移f[i][j]表示的是:使用i个精灵球和j的体力能够抓到多少小精灵。并不需要带入题目中的体力值为0时那个抓不到。
体力为0抓不到表示的是不能把所有体力消耗完成,所以最后取得是f[n][k - 1]的值。并不会影响状态转移。
请问~k的具体意思是啥?
等价于
k >= 0
因为
可以在编译器下试一试
知道了,谢谢。
~k
应该等价于k!=-1
,不过在这个for循环里两者作用是一样的时空复杂度??
学费了
大佬666
这一段里面我觉得不需要从k开始枚举吧,因为你枚举到第i个物品的话当前最多也只能选i个吧
希望博主回复一下/kel
可以优化的
ac了就行
主要是怕越界QAQ
担心出现无意义转化
人脑差别有这么大吗orz
Orz
想问一下,大佬,为什么你可以这么优化呢,为什么用的精灵球数最少就一定可以满足要求呢
有最优子结构