为何大重量0/1背包修改代码仅部分测试用例生效？

问题描述 #

有N个物品，编号为1、2、……、N。对于每个物品i（1 ≤ i ≤ N）：

• 重量为w[i]
• 价值为v[i]
  太郎要从这些物品里挑选一部分放进背包带回家，背包的容量为W，即所选物品的总重量必须不超过W。你的任务是求出太郎能带回家的物品的最大总价值。

输入约束 #

输入中的所有值均为整数：

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 10^5
• 1 ≤ w[i] ≤ W
• 1 ≤ v[i] ≤ 10^9

我的问题 #

我搞不懂为什么我的解决方案无法正常运行。

我现在要解决的是一个0/1背包问题，这个问题的重量上限是10^{9，价值上限是10}3。之前我写过另一个类似背包问题的代码，那个问题重量上限是10^{5，价值上限是10}9，代码能正常工作。

适用于另一个问题的代码：

#include<bits/stdc++.h>
using namespace std;

long long pr(long long weight[], long long profit[], long long n, long long w, vector<vector<long long>> &dp);

int main(){
    long long n, w;
    cin>>n;
    cin>>w;

    long long weight[n], profit[n];
    vector<vector<long long>> dp(n+1, vector<long long>(w+1, -1));
    for(int i=0; i<n; i++){
        cin>>weight[i];
        cin>>profit[i];
    } 

    cout<<pr(weight, profit, n , w, dp);

    return 0;
}

long long pr(long long weight[], long long profit[], long long n, long long w, vector<vector<long long>> &dp){
    if(n==0 or w==0){
        dp[n][w] = 0;
        return 0;
    }

    if(weight[n-1]>w){
        if(dp[n][w]<0) dp[n][w] = pr(weight, profit, n-1, w, dp);
        return dp[n][w];
    }

    if(dp[n][w]<0) dp[n][w] = max(profit[n-1] + pr(weight, profit, n-1, w-weight[n-1], dp), pr(weight, profit, n-1, w, dp));

    return dp[n][w];
}

我对代码做了少量修改来适配当前问题：

#include<bits/stdc++.h>
using namespace std;

long long pr(long long weight[], long long profit[], long long n, long long w, vector<vector<long long>> &dp, long long total);

int main(){
    long long n, w;
    cin>>n;
    cin>>w;

    long long weight[n], profit[n];
    long long total_profit = 0;
    for(int i=0; i<n; i++){
        cin>>weight[i];
        cin>>profit[i];
        total_profit+=profit[i];
    } 

    vector<vector<long long>> dp(n+1, vector<long long>(total_profit+1, -1));

    cout<<pr(weight, profit, n , w, dp, total_profit);

    return 0;
}

long long pr(long long weight[], long long profit[], long long n, long long w, vector<vector<long long>> &dp, long long total){
    if(n==0 or total==0){
        dp[n][total] = 0;
        return 0;
    }

    if(weight[n-1]>w){
        if(dp[n][total]<0) dp[n][total] = pr(weight, profit, n-1, w, dp, total);
        return dp[n][total];
    }

    if(dp[n][total]<0) dp[n][total] = max(profit[n-1] + pr(weight, profit, n-1, w - weight[n-1], dp, total), pr(weight, profit, n-1, w, dp, total - profit[n-1]));

    return dp[n][total];
}

现在这段代码对部分输入有效，比如：

6 15
6 5
5 6
6 4
6 6
3 5
7 2

但对vjudge的测试用例无效，我完全搞不懂原因。

内容的提问来源于stack exchange，提问作者Plague