关于记忆化搜索程序求调
一道题目求调，关于记忆化搜索https://www.luogu.com.cn/problem/P1060
另外，有谁可以推荐一个免费chatgpt镜像吗，谢谢了
#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
long long v,p,mem;
long long dp(int x,int s)
{
if(mem!=0) return mem;
if(x==0)
{
if(v>s)
{
return 0;
}
return v*p;
}
if(v>s)
{
mem=dp(x-1,s);
return mem;
}
if(mem]==0) mem]=v*p+dp(x-1,s-v);
if(mem==0) mem=dp(x-1,s);
return max(mem],mem);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%lld%lld",&v,&p);
}
printf("%lld\n",dp(m-1,n));
return 0;
}
主要是看记忆化哪里逻辑不对，我一直找不到
@zhangjinxuan @元豪 @sfqxx 别问我，我不会{:10_284:} 可不可以用贪心？ 元豪 发表于 2023-7-7 06:56
可不可以用贪心？
额，好像不行{:10_284:}
算了 @zhangjinxuan 题不会，镜像还是可以给你的
https://c.binjie.fun/ liuhongrun2022 发表于 2023-7-7 08:24
题不会，镜像还是可以给你的
https://c.binjie.fun/
github.com/xx025/carrot
你看issue，这个还是我提的，是在jinshutuan被墙那天偶然在jinshutuan上看见的
然后jinshutuan当天下午就无法访问了
于是我就去了cbinjiefun，过了几天看github.com/xx025/carrot上还没有就顺便提了一个issue 这个就是背包问题，可以使用动态规划来解决。
首先，创建一个二维数组dp，其中dp表示在考虑前i件物品、总钱数不超过j的情况下，所能达到的最大总和。
然后，我们可以使用以下递推关系式来填充dp数组：
dp = max(dp, dp] + v*w)
其中v表示第i件物品的价格，w表示第i件物品的重要度。
最后，所求的答案即为dp。
C++代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, m;
cin >> N >> m;
vector<int> v(m+1);
vector<int> w(m+1);
vector<vector<int>> dp(m+1, vector<int>(N+1));
for (int i = 1; i <= m; i++) {
cin >> v >> w;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= N; j++) {
if (j >= v) {
dp = max(dp, dp] + v*w);
} else {
dp = dp;
}
}
}
cout << dp << endl;
return 0;
}
（CHATGPT国内版）
https://www.wetab.link/
这个是浏览器插件，目前使用体验还是非常好的。（其会修改新标签页，请允许及插件行为）
需要登录。登录后里面有个Chat AI，点进去就可以问问题。
求最佳答案！ 元豪 发表于 2023-7-7 06:56
可不可以用贪心？
不行吧。 python/print 发表于 2023-7-7 12:59
这个就是背包问题，可以使用动态规划来解决。
首先，创建一个二维数组dp，其中dp表示在考虑 ...
但我提问的主要目的是看我思维逻辑哪里有问题，算出来答案为什么不同 本帖最后由 python/print 于 2023-7-8 13:25 编辑
额外减小 发表于 2023-7-7 18:03
但我提问的主要目的是看我思维逻辑哪里有问题，算出来答案为什么不同
（求最佳答案）
这段代码是背包问题的解法，但是存在以下几处错误：
1. 在主函数中，读入的物品个数m应该为m+1，因为物品的编号是从0到m-1。所以第一个循环应该是for(int i=0;i<=m;i++)。
2. 在dp函数中，第一个if条件语句判断v与s的大小关系时，应该是if(v>s)，而不是if(v>=s)，因为根据题目描述，可以等于总钱数N。
3. 在第一个if条件语句中，需要添加对mem的更新，即mem = v * p;，以确保初始问题的结果被正确保存到mem数组中。
(没办法，上面貌似和论坛的冲突了，只能用代码框)
代码如下：
#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
long long v,p,mem;
long long dp(int x,int s)
{
if(mem!=0) return mem;
if(x==0)
{
if(v>s)
{
return 0;
}
mem = v * p; // 更新初始问题的结果
return mem;
}
if(v>s)
{
mem=dp(x-1,s);
return mem;
}
if(mem]==0) mem]=v*p+dp(x-1,s-v);
if(mem==0) mem=dp(x-1,s);
return max(mem],mem);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=m;i++) // 修改循环条件
{
scanf("%lld%lld",&v,&p);
}
printf("%lld\n",dp(m,n)); // 修改参数传递
return 0;
}
但是 这个思路可能还是解不了一些节点，我也不知道怎么回事，WA了，但是按照下方思路来，我试过是AC的{:5_104:}
这个就是背包问题，可以使用动态规划来解决。
首先，创建一个二维数组dp，其中dp表示在考虑前i件物品、总钱数不超过j的情况下，所能达到的最大总和。
然后，我们可以使用以下递推关系式来填充dp数组：
dp = max(dp, dp + v*w)
其中v表示第i件物品的价格，w表示第i件物品的重要度。
最后，所求的答案即为dp。
python/print 发表于 2023-7-8 13:16
（求最佳答案）
你确定不是用chatgpt回答的吧。这个回答的语言逻辑上可能有点问题。不过我试了下顺推还是能过的，那就给你最佳了 额外减小 发表于 2023-7-10 15:50
你确定不是用chatgpt回答的吧。这个回答的语言逻辑上可能有点问题。不过我试了下顺推还是能过的，那就给 ...
GPT一般会回答这个是典型的xxx问题
页:
[1]