[已解决]关于记忆化搜索程序求调

额外减小

一道题目求调，关于记忆化搜索
https://www.luogu.com.cn/problem/P1060

另外，有谁可以推荐一个免费chatgpt镜像吗，谢谢了

1. #include <stdio.h>
   
2. #define max(a,b) (a)>(b)?(a):(b)
   
3. 
   
4. long long v[28],p[28],mem[28][30001];
   
5. 
   
6. long long dp(int x,int s)
   
7. {
   
8.         if(mem[x][s]!=0) return mem[x][s];
   
9.         if(x==0)
   
10.         {
    
11.                 if(v[0]>s)
    
12.                 {
    
13.                         return 0;
    
14.                 }
    
15.                 return v[0]*p[0];
    
16.         }
    
17.        
    
18.         if(v[x]>s)
    
19.         {
    
20.                 mem[x-1][s]=dp(x-1,s);
    
21.                 return mem[x-1][s];
    
22.         }
    
23.         if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
    
24.         if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
    
25.         return max(mem[x-1][s-v[x]],mem[x-1][s]);
    
26. }
    
27. 
    
28. int main()
    
29. {
    
30.         int n,m;
    
31.         scanf("%d%d",&n,&m);
    
32.         for(int i=0;i<m;i++)
    
33.         {
    
34.                 scanf("%lld%lld",&v[i],&p[i]);
    
35.         }
    
36.         printf("%lld\n",dp(m-1,n));
    
37.         return 0;
    
38. }

复制代码

主要是看记忆化哪里逻辑不对，我一直找不到
@zhangjinxuan @元豪 @sfqxx

最佳答案

月排行榜 / 总排行榜

python/print

2023-7-8 13:16:59

额外减小 发表于 2023-7-7 18:03
但我提问的主要目的是看我思维逻辑哪里有问题，算出来答案为什么不同

（求最佳答案）

1. 这段代码是背包问题的解法，但是存在以下几处错误：
   
2. 1. 在主函数中，读入的物品个数m应该为m+1，因为物品的编号是从0到m-1。所以第一个循环应该是for(int i=0;i<=m;i++)。
   
3. 2. 在dp函数中，第一个if条件语句判断v[0]与s的大小关系时，应该是if(v[0]>s)，而不是if(v[0]>=s)，因为根据题目描述，可以等于总钱数N。
   
4. 3. 在第一个if条件语句中，需要添加对mem[0][s]的更新，即mem[0][s] = v[0] * p[0];，以确保初始问题的结果被正确保存到mem数组中。

复制代码

1. (没办法，上面[s]貌似和论坛的冲突了，只能用代码框)

复制代码

代码如下：

1. #include <stdio.h>
   
2. #define max(a,b) (a)>(b)?(a):(b)
   
3. 
   
4. long long v[28],p[28],mem[28][30001];
   
5. 
   
6. long long dp(int x,int s)
   
7. {
   
8.         if(mem[x][s]!=0) return mem[x][s];
   
9.         if(x==0)
   
10.         {
    
11.                 if(v[0]>s)
    
12.                 {
    
13.                         return 0;
    
14.                 }
    
15.                 mem[0][s] = v[0] * p[0]; // 更新初始问题的结果
    
16.                 return mem[0][s];
    
17.         }
    
18.         
    
19.         if(v[x]>s)
    
20.         {
    
21.                 mem[x-1][s]=dp(x-1,s);
    
22.                 return mem[x-1][s];
    
23.         }
    
24.         if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
    
25.         if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
    
26.         return max(mem[x-1][s-v[x]],mem[x-1][s]);
    
27. }
    
28. 
    
29. int main()
    
30. {
    
31.         int n,m;
    
32.         scanf("%d%d",&n,&m);
    
33.         for(int i=0;i<=m;i++) // 修改循环条件
    
34.         {
    
35.                 scanf("%lld%lld",&v[i],&p[i]);
    
36.         }
    
37.         printf("%lld\n",dp(m,n)); // 修改参数传递
    
38.         return 0;
    
39. }

复制代码

但是 这个思路可能还是解不了一些节点，我也不知道怎么回事，WA了，但是按照下方思路来，我试过是AC的

1. 这个就是背包问题，可以使用动态规划来解决。
   
2. 首先，创建一个二维数组dp[m+1][N+1]，其中dp[j]表示在考虑前i件物品、总钱数不超过j的情况下，所能达到的最大总和。
   
3. 然后，我们可以使用以下递推关系式来填充dp数组：
   
4. dp[j] = max(dp[i-1][j], dp[i-1][j-v] + v*w)
   
5. 其中v表示第i件物品的价格，w表示第i件物品的重要度。
   
6. 最后，所求的答案即为dp[m][N]。

复制代码

跳转到最佳答案楼层

元豪

别问我，我不会

元豪

可不可以用贪心？

元豪

元豪 发表于 2023-7-7 06:56
可不可以用贪心？

额，好像不行

算了 @zhangjinxuan

liuhongrun2022

题不会，镜像还是可以给你的
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

python/print

这个就是背包问题，可以使用动态规划来解决。
首先，创建一个二维数组dp[m+1][N+1]，其中dp[i][j]表示在考虑前i件物品、总钱数不超过j的情况下，所能达到的最大总和。
然后，我们可以使用以下递推关系式来填充dp数组：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]*w[i])
其中v[i]表示第i件物品的价格，w[i]表示第i件物品的重要度。
最后，所求的答案即为dp[m][N]。
C++代码如下：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int main() {
   
8.     int N, m;
   
9.     cin >> N >> m;
   
10. 
    
11.     vector<int> v(m+1);
    
12.     vector<int> w(m+1);
    
13.     vector<vector<int>> dp(m+1, vector<int>(N+1));
    
14. 
    
15.     for (int i = 1; i <= m; i++) {
    
16.         cin >> v[i] >> w[i];
    
17.     }
    
18. 
    
19.     for (int i = 1; i <= m; i++) {
    
20.         for (int j = 1; j <= N; j++) {
    
21.             if (j >= v[i]) {
    
22.                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]*w[i]);
    
23.             } else {
    
24.                 dp[i][j] = dp[i-1][j];
    
25.             }
    
26.         }
    
27.     }
    
28. 
    
29.     cout << dp[m][N] << endl;
    
30. 
    
31.     return 0;
    
32. }

复制代码

（CHATGPT国内版）

1. https://www.wetab.link/

复制代码

这个是浏览器插件，目前使用体验还是非常好的。（其会修改新标签页，请允许及插件行为）
需要登录。登录后里面有个Chat AI，点进去就可以问问题。

求最佳答案！

额外减小

元豪 发表于 2023-7-7 06:56
可不可以用贪心？

不行吧。

额外减小

python/print 发表于 2023-7-7 12:59
这个就是背包问题，可以使用动态规划来解决。
首先，创建一个二维数组dp[m+1][N+1]，其中dp[j]表示在考虑 ...

但我提问的主要目的是看我思维逻辑哪里有问题，算出来答案为什么不同

python/print

额外减小 发表于 2023-7-7 18:03
但我提问的主要目的是看我思维逻辑哪里有问题，算出来答案为什么不同

（求最佳答案）

1. 这段代码是背包问题的解法，但是存在以下几处错误：
   
2. 1. 在主函数中，读入的物品个数m应该为m+1，因为物品的编号是从0到m-1。所以第一个循环应该是for(int i=0;i<=m;i++)。
   
3. 2. 在dp函数中，第一个if条件语句判断v[0]与s的大小关系时，应该是if(v[0]>s)，而不是if(v[0]>=s)，因为根据题目描述，可以等于总钱数N。
   
4. 3. 在第一个if条件语句中，需要添加对mem[0][s]的更新，即mem[0][s] = v[0] * p[0];，以确保初始问题的结果被正确保存到mem数组中。

复制代码

1. (没办法，上面[s]貌似和论坛的冲突了，只能用代码框)

复制代码

代码如下：

1. #include <stdio.h>
   
2. #define max(a,b) (a)>(b)?(a):(b)
   
3. 
   
4. long long v[28],p[28],mem[28][30001];
   
5. 
   
6. long long dp(int x,int s)
   
7. {
   
8.         if(mem[x][s]!=0) return mem[x][s];
   
9.         if(x==0)
   
10.         {
    
11.                 if(v[0]>s)
    
12.                 {
    
13.                         return 0;
    
14.                 }
    
15.                 mem[0][s] = v[0] * p[0]; // 更新初始问题的结果
    
16.                 return mem[0][s];
    
17.         }
    
18.         
    
19.         if(v[x]>s)
    
20.         {
    
21.                 mem[x-1][s]=dp(x-1,s);
    
22.                 return mem[x-1][s];
    
23.         }
    
24.         if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
    
25.         if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
    
26.         return max(mem[x-1][s-v[x]],mem[x-1][s]);
    
27. }
    
28. 
    
29. int main()
    
30. {
    
31.         int n,m;
    
32.         scanf("%d%d",&n,&m);
    
33.         for(int i=0;i<=m;i++) // 修改循环条件
    
34.         {
    
35.                 scanf("%lld%lld",&v[i],&p[i]);
    
36.         }
    
37.         printf("%lld\n",dp(m,n)); // 修改参数传递
    
38.         return 0;
    
39. }

复制代码

但是 这个思路可能还是解不了一些节点，我也不知道怎么回事，WA了，但是按照下方思路来，我试过是AC的

1. 这个就是背包问题，可以使用动态规划来解决。
   
2. 首先，创建一个二维数组dp[m+1][N+1]，其中dp[j]表示在考虑前i件物品、总钱数不超过j的情况下，所能达到的最大总和。
   
3. 然后，我们可以使用以下递推关系式来填充dp数组：
   
4. dp[j] = max(dp[i-1][j], dp[i-1][j-v] + v*w)
   
5. 其中v表示第i件物品的价格，w表示第i件物品的重要度。
   
6. 最后，所求的答案即为dp[m][N]。

复制代码

额外减小

python/print 发表于 2023-7-8 13:16
（求最佳答案）

你确定不是用chatgpt回答的吧。这个回答的语言逻辑上可能有点问题。不过我试了下顺推还是能过的，那就给你最佳了

python/print

额外减小 发表于 2023-7-10 15:50
你确定不是用chatgpt回答的吧。这个回答的语言逻辑上可能有点问题。不过我试了下顺推还是能过的，那就给 ...

GPT一般会回答这个是典型的xxx问题