01背包，我用记忆化搜索做，爆零了
本帖最后由 zhangjinxuan 于 2022-11-14 21:32 编辑有一天做 01背包， 我先写了一个记忆化搜索，但是一个测试点都没有过，样例和自己造的一个小数据都过了，为什么呢？
这是我的代码，到底哪儿出了问题呢？
#include <bits/stdc++.h>
using namespace std;
int n, m, f, ans, gw, gv;
int dfs(int i, int v, int w) {
if (v == 0) return w;
if (i == n + 1) return w;
if (f) return f;
f = dfs(i + 1, v, w);
if (v >= gv) {
f = max(f, dfs(i + 1, v - gv, w + gw));
}
return f;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &gv, &gw);
}
printf("%d", dfs(1, m, 0));
}
原题：
有人吗？谁收藏的？是想慢慢研究吗{:10_256:} 没过的测试点的输入数据是什么？
你得知道输入是什么，输入了什么导致你的程序给出了错误的结果？
没办法重现的问题基本无解
人造人 发表于 2022-11-14 21:21
没过的测试点的输入数据是什么？
你得知道输入是什么，输入了什么导致你的程序给出了错误的结果？
没办法 ...
我不知道，测试点没有公开 zhangjinxuan 发表于 2022-11-14 21:25
我不知道，测试点没有公开
无解
人造人 发表于 2022-11-14 21:21
没过的测试点的输入数据是什么？
你得知道输入是什么，输入了什么导致你的程序给出了错误的结果？
没办法 ...
知道我肯定会说出来的，明天再说吧，今天有点晚了 if(v == 0) return w;
价值为0的时候返回体积？
什么意思？ printf("%d\n", dfs(1, m, 0));
m是什么？体积？
把m传给v ？
把体积传给价值？
我表示看不懂
https://blog.csdn.net/Iseno_V/article/details/100001133 人造人 发表于 2022-11-14 21:26
if(v == 0) return w;
价值为0的时候返回体积？
什么意思？
不好意思，没有给原题：
人造人 发表于 2022-11-14 21:30
https://blog.csdn.net/Iseno_V/article/details/100001133
我会DP的01背包，但我就是想问一下这个代码为什么不行？ zhangjinxuan 发表于 2022-11-14 21:32
不好意思，没有给原题：
所以说v和w到底是体积和价值还是价值和体积？
怎么同一个问题整出两个完全不同的概念来？
人造人 发表于 2022-11-14 21:36
所以说v和w到底是体积和价值还是价值和体积？
怎么同一个问题整出两个完全不同的概念来？
原题说了的啊？v是体积，w是收益 我研究研究吧
首先你要明白，无法重现的问题基本上无法解决
人造人 发表于 2022-11-14 21:43
我研究研究吧
首先你要明白，无法重现的问题基本上无法解决
感谢大佬提醒 本帖最后由 柿子饼同学 于 2022-11-15 18:38 编辑
这就别管了吧
用正常的方法做吧 , 记忆化可能不稳定
我已经退役了...{:10_266:} 柿子饼同学 发表于 2022-11-15 18:36
这就别管了吧
用正常的方法做吧 , 记忆化可能不稳定
我已经退役了...
好，感谢前辈提醒，我会加油的！ zhangjinxuan 发表于 2022-11-15 19:23
好，感谢前辈提醒，我会加油的！
明年 , 祝你一等奖
要好好努力了{:10_265:}
页:
[1]