01背包问题：求等长子和

Question

#define inf -1
#define maxn 201
#define maxv 20000

//numsSize件物品放到一个背包里，如果背包里物品价值是总价值的1/2，则表示可以分成两个等和子集
int opt(int a,int b){
    if(a==inf) return b;
    if(b==inf) return a;
    return a>b?a:b;
}


bool myBag(int n,int* a,int* dp){//dp表示容量为j的背包最大价值是多少
    int sumv=0;
    for(int i=0;i<n;i++){
        sumv+=a[i];
    }
    if(sumv%2==1) return false;
    for(int i=1;i<=maxn;i++){
        dp[i]=inf;
    }
    dp[0]=0;
    int maxcapacity=sumv/2;
    for(int i=0;i<n;i++){//把编号为i的物品放到容量为j的背包
        for(int j=n-1;j>=1&&dp[j-1]+a[i]<=maxcapacity;j--){
            dp[j]=opt(dp[j],dp[j-1]+a[i]);//if dp[j]==dp[j]表示该物品不放入背包 if dp[j]=dp[j-1]+a[i]表示这件物品放入背包    
            if(dp[j]==maxcapacity) return true;
         }
    }
    
    return false;
}

int dp[maxv];

bool canPartition(int* nums, int numsSize) {
    return myBag(numsSize,nums,dp);
}

为什么不对呀🥹

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题解答

问题描述 求等长子和：定义了一个背包问题，需要将numsSize件物品放到一个背包里，如果背包里物品价值是总价值的1/2，则表示可以分成两半。

解决方案 这个问题可以使用动态规划来解决。我们可以使用一个二维数组dp[i][j]，其中dp[i][j]表示将前i件物品放入背包中，总价值为j的可能性。

#include <iostream>
#include <vector>
using namespace std;

int backPack(int numsSize, vector<int>& nums) {
    int total = 0;
    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }
    if (total % 2 != 0) {
        return -1; //总价值不是偶数
    }
    int target = total / 2;
    vector<vector<bool>> dp(numsSize + 1, vector<bool>(target + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= numsSize; i++) {
        for (int j = target; j >= 0; j--) {
            dp[i][j] = dp[i - 1][j];
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    for (int i = target; i >= 0; i--) {
        if (dp[numsSize][i]) {
            return i;
        }
    }
    return -1; //找不到
}

int main() {
    int numsSize = 5;
    vector<int> nums = {1, 2, 3, 4, 5};
    int result = backPack(numsSize, nums);
    cout << result << endl;
    return 0;
}

解释 我们首先计算总价值total，然后判断总价值是否是偶数，如果不是，则返回-1。否则，我们使用动态规划来计算可以将前i件物品放入背包中，总价值为target的可能性。最后，我们遍历target，从后往前找到第一个可以将前i件物品放入背包中，总价值为target的可能性，然后返回该值。

注意 这个问题的时间复杂度是O(numsSize * target)，空间复杂度是O(numsSize * target)。