时间戳

首页 > 解决方案 > 为什么在 0-1 背包问题中我们使用 INT_MIN 以及为什么 0 不起作用

algorithm - 为什么在 0-1 背包问题中我们使用 INT_MIN 以及为什么 0 不起作用

问题描述

为什么在 0-1 背包问题中 INT_min 用于 (max<0) 的返回语句中我尝试用 0 代替 INT_MIN 但我得到 65 而不是正确答案 60 为什么会发生这种情况请任何人解释一下这是背包问题的递归代码

#include<iostream>
using namespace std;
int solve(int v[],  int w[] , int n ,int max){
    if (max < 0) {
        return INT_MIN;      // here this is giving me problem if I use 0 in place of 
                            // INT_min I get wrong ansewrs
    }
 
    if (n < 0 || max == 0) {
        return 0;
    }
    
    int include = 0 ; 
    int exclude = 0 ;
    include = v[n]+solve(v,w, n-1,max - w[n]); 
    exclude = solve(v,w, n-1,max); 
    
    if(include<exclude){
        return exclude;
    }else{
        return include;
    }
}
int main(){
    int v[] = { 20, 5, 10, 40, 15, 25 };
    int w[] = { 1, 2, 3, 8, 7, 4 };
    int W = 10;
 
    int n = sizeof(v) / sizeof(v[0]);

    cout<< solve(v,w,n-1,W)<<endl;
    return 0;
}

对于这个数组，如果我在返回语句中使用 INT_MIN，我得到答案 60，如果我在返回语句中使用 0，我得到 65。

标签： algorithmdata-structuresknapsack-problem

解决方案

假设我们正在手动模拟递归过程。

首先，我们选择最后一个对象 ( v=25, w=4) 并丢弃最后一个对象 ( 15v, 7w)。现在我们有 25 个值和 4 个权重。之后，在 N 是对象数的下一步N-3中，我们将确定是否包括最后第三个对象 ( 40v, 8w)。

然后是当前步骤中的两个后续递归调用：

include = 40+solve(v,w, N-4,(10 - 4) - 8);
exclude = solve(v,w, N-4,(10-4));

如果在,INT_MIN时返回。和。这意味着不能拾取最后三分之一的物体，因为它会溢出背包，考虑到当前的剩余容量仅为.max < 0include = 40 + INT_MIN = SOME_EXTREMELY_SMALL_VALUEexclude = SOME_NON_ZERO_VALUE > include10-4=6

如果0返回，则include = 40+0=40. 和exclude = SOME_VALUE < 40。这意味着实际上除了最后一个对象之外还拾取了最后一个第三个对象，即使它刚刚超出背包，导致总重量为4+8=12>10和无效的答案40+25=65。

推荐阅读