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

额外减小

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

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

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

long long v[28],p[28],mem[28][30001];

long long dp(int x,int s)
{
        if(mem[x][s]!=0) return mem[x][s];
        if(x==0)
        {
                if(v[0]>s)
                {
                        return 0;
                }
                return v[0]*p[0];
        }
        
        if(v[x]>s)
        {
                mem[x-1][s]=dp(x-1,s);
                return mem[x-1][s];
        }
        if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
        if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
        return max(mem[x-1][s-v[x]],mem[x-1][s]);
}

int main()
{
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
                scanf("%lld%lld",&v[i],&p[i]);
        }
        printf("%lld\n",dp(m-1,n));
        return 0;
}

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

最佳答案

月排行榜 / 总排行榜

python/print

2023-7-8 13:16:59

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

（求最佳答案）

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

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

代码如下：

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

long long v[28],p[28],mem[28][30001];

long long dp(int x,int s)
{
        if(mem[x][s]!=0) return mem[x][s];
        if(x==0)
        {
                if(v[0]>s)
                {
                        return 0;
                }
                mem[0][s] = v[0] * p[0]; // 更新初始问题的结果
                return mem[0][s];
        }
        
        if(v[x]>s)
        {
                mem[x-1][s]=dp(x-1,s);
                return mem[x-1][s];
        }
        if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
        if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
        return max(mem[x-1][s-v[x]],mem[x-1][s]);
}

int main()
{
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=m;i++) // 修改循环条件
        {
                scanf("%lld%lld",&v[i],&p[i]);
        }
        printf("%lld\n",dp(m,n)); // 修改参数传递
        return 0;
}

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

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

#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[i] >> w[i];
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= N; j++) {
            if (j >= v[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]*w[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[m][N] << endl;

    return 0;
}

（CHATGPT国内版）

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

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

代码如下：

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

long long v[28],p[28],mem[28][30001];

long long dp(int x,int s)
{
        if(mem[x][s]!=0) return mem[x][s];
        if(x==0)
        {
                if(v[0]>s)
                {
                        return 0;
                }
                mem[0][s] = v[0] * p[0]; // 更新初始问题的结果
                return mem[0][s];
        }
        
        if(v[x]>s)
        {
                mem[x-1][s]=dp(x-1,s);
                return mem[x-1][s];
        }
        if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
        if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
        return max(mem[x-1][s-v[x]],mem[x-1][s]);
}

int main()
{
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=m;i++) // 修改循环条件
        {
                scanf("%lld%lld",&v[i],&p[i]);
        }
        printf("%lld\n",dp(m,n)); // 修改参数传递
        return 0;
}

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

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

额外减小

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

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

python/print

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

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