01背包，最后一块石头

Question

#define maxv 3001
#define inf 0//-1
//看成两个包里的石头互相碰，记一个包是k=-1，记另一个是k=1，则k=-1的包在容量不超过sum/2的情况下的最大值
int opt(int a,int b){
    if(a==inf) return b;
    if(b==inf) return a;
    return a>b?a:b; 
}


int myBag(int n,int* a,int* dp){
    for(int i=1;i<maxv;i++){
        dp[i]=inf;
    }
    dp[0]=0;
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
    }
    for(int i=0;i<n;i++){
        for(int j=sum/2;j-a[i]>=0;j--){//j从sum/2开始倒序计算已经规定容量不能超过sum/2
          dp[j]=opt(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    int bag1=dp[sum/2];
    printf("%d\n",bag1);
    int bag2=sum-bag1;
    return bag2-bag1;
}
int dp[maxv];
int lastStoneWeightII(int* stones, int stonesSize) {
    return myBag(stonesSize,stones,dp);
}

为什么inf定义成-1就不对呢

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题出在定义inf为-1时，在opt函数中判断条件是if(a==inf)和if(b==inf)，但是inf定义为-1时，实际上a和b都不可能等于-1，所以这两个条件永远不会成立，导致程序逻辑错误。应该将inf定义为一个较大的数，例如INT_MAX。 修改代码如下：

#define maxv 3001
#define inf INT_MAX
int opt(int a, int b){
    if(a==inf) return b;
    if(b==inf) return a;
    return a>b ? a : b;
}
int myBag(int n, int* a, int* dp){
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += a[i];
    }
    for(int i=0; i<maxv; i++){
        dp[i] = inf;
    }
    dp[0] = 0;
    for(int i=0; i<n; i++){
        for(int j=sum/2; j-a[i]>=0; j--){
            dp[j] = opt(dp[j], dp[j-a[i]]+a[i]);
        }
    }
    int bag1 = dp[sum/2];
    printf("%d\n", bag1);
    int bag2 = sum - bag1;
    return bag2 - bag1;
}
int dp[maxv];
int lastStoneWeightII(int* stones, int stonesSize) {
    return myBag(stonesSize, stones, dp);
}