时间戳

首页 > 解决方案 > 使用大数字时背包没有给出正确的输出

c++ - 使用大数字时背包没有给出正确的输出

问题描述

在开始这个问题之前，让我自我介绍一下。我是一名移动开发人员，目前在华沙工作，并将空闲时间用于准备面试。两年前我开始准备面试。那时我应该说我不能解决二和问题。在我看来，简单的问题就像困难的问题，所以大部分时间我不得不看社论和讨论部分。目前，我已经解决了大约 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;
}

标签： c++knapsack-problem

解决方案

这取决于您的工具链和平台，但很可能您的值溢出，因为您的预期输出高于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 个问题并错过了溢出之类的东西，这实际上是令人震惊的，如果我不得不猜测，我猜这可能会在面试时对你不利。

至少大致了解类型何时可能溢出，这些在平台上会发生变化。或浮点/双精度类型的失败模式以及应避免的情况。什么是易变的等等......了解语言的基础知识比知道如何解决一些抽象的数学问题更有价值。

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

我从多行 knapSackRec 变量中删除了缩进，我也喜欢在逻辑上将参数拆分为多行，但是然后始终以这种方式使用它。养成在某些地方（以及有多少）放置换行符的习惯。或者也许学习 MISRA 并能够使用它进行编码，例如，如果您在面试中解决编码问题并声明这是 MISRA C 的恭维，那么我会印象深刻。不仅仅是有代码可以工作，但不明白为什么，不明白什么时候会失败（比如溢出），而且很难阅读。

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

知道如何编写解决方案并使其发挥作用是很棒的，但如果你愿意在面试中提出现在你可以清理它并重新编写它以完全符合 MISRA C（或其他标准）的恭维，那么我认为任何面试官都应该给你奖励积分。

推荐阅读