使用大数字时，背包无法提供正确的输出

Question

在开始提问之前，让我先自我介绍一下。我是一名移动开发人员，目前在华沙工作，将空闲时间花在面试准备上。我两年前就开始准备面试了。当时我应该说我不能解决两和问题。在我看来，简单的问题就像困难的问题，所以大多数时候我不得不看社论和讨论章节。目前，我已经解决了大约800个问题，并不时地参加比赛。我通常在一次竞赛中解决3道题，有时也会解决4道题。好了，让我们回到主题上来。

这里是自顶向下的动态编程方法，knapSackRec是递归实现的。但它在给定的测试用例上不起作用：

W=5,
n=5,
wt{1,1,1,1,1},
v{1000000000,1000000000,1000000000,1000000000,1000000000,}

它返回2000000000作为输出。但是正确的输出应该是5000000000。

我的代码如下：

#include <bits/stdc++.h>
using namespace std;
int static dp[102][1000005];

// Returns the value of maximum profit
int knapSackRec(int W, int wt[], int val[], int i)
{
    // Base condition
    if (i < 0)
        return 0;

    if (dp[i][W] != -1)
        return dp[i][W];

    if (wt[i] > W) 
    {
        // Store the value of function call
        // stack in table before return

        return dp[i][W] = knapSackRec(W, wt, val, i - 1);
    }
    else 
    {
        // Store value in a table before return

        // Return value of table after storing
        return dp[i][W] = max(
                val[i] + knapSackRec(W - wt[i], wt, val, i - 1),
                knapSackRec(W, wt, val, i - 1)
        );
    }
}
    
int main()
{
    int val[] = { 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 };
    int wt[]  = { 1, 1, 1, 1, 1 };
    int W = 5;
    int n = sizeof(val) / sizeof(val[0]);
    memset(dp, -1, sizeof(dp));

    cout << knapSackRec(W, wt, val, n);
    return 0;
}

Answer 1

这取决于您的工具链和平台，但最有可能的情况是您的值溢出，因为您的预期输出高于INT_MAX (我将假定使用x86平台)。顺便说一句，这些技术信息(操作系统，平台，版本的东西)对我们来说比你的生活背景更有价值。

查看其他类型的范围：

https://docs.microsoft.com/en-us/cpp/c-language/cpp-integer-limits?view=msvc-160

INT_MAX Maximum value for a variable of type int. 2147483647

你能试着运行这个吗：

#include <bits/stdc++.h>
using namespace std;
long long static dp[102][1000005];

// Returns the value of maximum profit
long long knapSackRec(long long W, long long wt[], long long val[], long long i)
{
    // Base condition
    if (i < 0)
        return 0;

    if (dp[i][W] != -1)
        return dp[i][W];

    if (wt[i] > W) 
    {
        // Store the value of function call
        // stack in table before return

        return dp[i][W] = knapSackRec(W, wt, val, i - 1);
    }
    else 
    {
        // Store value in a table before return

        // Return value of table after storing
        return dp[i][W] = max(
                val[i] + knapSackRec(W - wt[i], wt, val, i - 1),
                knapSackRec(W, wt, val, i - 1)
        );
    }
}
    
int main()
{
    long long val[] = { 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 };
    long long wt[]  = { 1, 1, 1, 1, 1 };
    long long W = 5;
    long long n = sizeof(val) / sizeof(val[0]);
    memset(dp, -1, sizeof(dp));

    cout << knapSackRec(W, wt, val, n);
    return 0;
}

至于你的面试准备，能够解决随机和晦涩的数学和算法问题是很好的，但用好的代码基础和好的编码风格来取代它并不是一件好事。实际上，声称解决了800个问题，却错过了溢出这样的东西，这实际上是令人震惊的，如果要我猜的话，我猜这可能会在面试中对你不利。

至少粗略地知道什么时候类型可能溢出，这些类型在平台上会发生变化。或float/double类型的失败模式以及要避免的问题。什么是易失性的，等等。了解语言的基础知识比知道如何解决一些抽象的数学问题更有价值。

我编辑了你的问题并解决了这些问题，但我建议你开发一种编码风格并坚持下去。你想在同一行还是下一行使用{，我不会争论其中之一，但选择一个并坚持下去，不要在一个函数中改变它。

我去掉了多行knapSackRec变量的缩进，我也喜欢将参数逻辑地拆分到多行，然后一直这样使用。养成在某些地方换行的习惯(以及其中有多少)。或者学习MISRA并能够使用它进行编码，例如，如果你在面试中解决了一个编码问题，并声明这是MISRA C称赞，那么我会真的印象深刻。不仅仅是代码可以正常工作，还有更多的原因，但是不能确切地理解为什么，不能理解什么时候会失败(比如溢出)，也很难阅读。

例如，MISRA C具有针对单个返回语句的规则：https://spin.atomicobject.com/2011/07/26/in-defence-of-misra/

知道如何编写解决方案并使其工作是很棒的，但如果你在面试中提出现在你可以清理它，并将其重写为完全MISRA C(或其他标准)的赞美，那么我认为任何面试官都应该为此给你加分。