代码随想录第三十六天（一刷&&C语言）|背包问题理论基础&&分割等和子集

创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。

一、背包问题

题目：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

思路：参考carl文档。

1、确定dp数组以及下标的含义：

（1）使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

（2）使用一维数组，dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]。

2、确定递推公式：

二维数组：

（1）不放物品i：背包容量为j，里面不放物品i的最大价值，推出dp[i - 1][j]。

（2）放物品i：dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，故背包放物品i得到的最大价值是dp[i - 1][j - weight[i]] + value[i] （物品i的价值）。

故递归公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。

一维数组：

????????dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。故而递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3、dp数组如何初始化：

二维数组：

????????由递推公式知i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

当 j < weight[0]时，既背包容量比编号0的物品重量还小，dp[0][j] 为是0。

当j >= weight[0]时，既背包容量放足够放编号0物品，dp[0][j] 应该是value[0]。

由递推公式知dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

一维数组：假设物品价值都是大于0的，dp数组初始化的时候，都初始为0。

4、确定遍历的维度：

二维数组：

有两个遍历的维度，物品与背包重量。先遍历背包或先遍历背包重量均可。

一维数组：一维dp遍历的时候，背包是从大到小。采用倒序遍历。

5、分别举例推导dp数组

二维数组AC代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ARR_SIZE(a) (sizeof((a)) / sizeof((a)[0]))
#define BAG_WEIGHT 4

void backPack(int* weights, int weightSize, int* costs, int costSize, int bagWeight) {
    // 开辟dp数组
    int dp[weightSize][bagWeight + 1];
    memset(dp, 0, sizeof(int) * weightSize * (bagWeight + 1));

    int i, j;
    // 当背包容量大于物品0的重量时，将物品0放入到背包中
    for(j = weights[0]; j <= bagWeight; ++j) {
        dp[0][j] = costs[0];
    }

    // 先遍历物品，再遍历重量
    for(j = 1; j <= bagWeight; ++j) {
        for(i = 1; i < weightSize; ++i) {
            // 如果当前背包容量小于物品重量
            if(j < weights[i])
                // 背包物品的价值等于背包不放置当前物品时的价值
                dp[i][j] = dp[i-1][j];
            // 若背包当前重量可以放置物品
            else
                // 背包的价值等于放置该物品或不放置该物品的最大值
                dp[i][j] = MAX(dp[i - 1][j],  dp[i - 1][j - weights[i]] + costs[i]);
        }
    }

    printf("%d\n", dp[weightSize - 1][bagWeight]);
}

int main(int argc, char* argv[]) {
    int weights[] = {1, 3, 4};
    int costs[] = {15, 20, 30};
    backPack(weights, ARR_SIZE(weights), costs, ARR_SIZE(costs), BAG_WEIGHT);
    return 0;
}

一维数组AC代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ARR_SIZE(a) (sizeof((a)) / sizeof((a)[0]))
#define BAG_WEIGHT 4

void backPack(int* weights, int weightSize, int* costs, int costSize, int bagWeight) {
    // 开辟dp数组
    int dp[weightSize][bagWeight + 1];
    memset(dp, 0, sizeof(int) * weightSize * (bagWeight + 1));

    int i, j;
    // 当背包容量大于物品0的重量时，将物品0放入到背包中
    for(j = weights[0]; j <= bagWeight; ++j) {
        dp[0][j] = costs[0];
    }

    // 先遍历物品，再遍历重量
    for(j = 1; j <= bagWeight; ++j) {
        for(i = 1; i < weightSize; ++i) {
            // 如果当前背包容量小于物品重量
            if(j < weights[i])
                // 背包物品的价值等于背包不放置当前物品时的价值
                dp[i][j] = dp[i-1][j];
            // 若背包当前重量可以放置物品
            else
                // 背包的价值等于放置该物品或不放置该物品的最大值
                dp[i][j] = MAX(dp[i - 1][j],  dp[i - 1][j - weights[i]] + costs[i]);
        }
    }

    printf("%d\n", dp[weightSize - 1][bagWeight]);
}

int main(int argc, char* argv[]) {
    int weights[] = {1, 3, 4};
    int costs[] = {15, 20, 30};
    backPack(weights, ARR_SIZE(weights), costs, ARR_SIZE(costs), BAG_WEIGHT);
    return 0;
}

二、分割等和子集

思路：参考carl文档。

本题要求集合里能否出现总和为 sum / 2 的子集。要理解题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。

（1）0/1背包问题

????????明确背包的体积为sum / 2。背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值。背包如果正好装满，说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。

（2）动规五部曲

1、确定dp数组以及下标的含义：?dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。若背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

2、确定递推公式：背包的递推公式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。题意相当于背包里放入数值，物品i的重量是nums[i]，其价值也是nums[i]。故而递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3、dp数组的初始化：从dp[j]的定义来看，dp[0]等于0。题目给的价值都是正整数那么非0下标都初始化为0，若题目给的价值有负数，那么非0下标就要初始化为负无穷。

4、确定遍历的顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历。

5、举例dp数组：明确如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j。

lecode题目：https://leetcode.cn/problems/partition-equal-subset-sum/description/

二维数组AC代码：

/**
1. dp数组含义：dp[i][j]为背包重量为j时，从[0-i]元素和最大值
2. 递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
3. 初始化：dp[i][0]初始化为0。因为背包重量为0时，不可能放入元素。dp[0][j] = nums[0]，当j >= nums[0] && j < target时
4. 遍历顺序：先遍历物品，再遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

    int i;
    for(i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;

    // 若子数组的和等于target，则nums可以被分割
    int target = sum / 2;
    // 初始化dp数组
    int dp[numsSize][target + 1];
    // dp[j][0]都应被设置为0。因为当背包重量为0时，不可放入元素
    memset(dp, 0, sizeof(int) * numsSize * (target + 1));

    int i, j;
    // 当背包重量j大于nums[0]时，可以在dp[0][j]中放入元素nums[0]
    for(j = nums[0]; j <= target; ++j) {
        dp[0][j] = nums[0];
    }

    for(i = 1; i < numsSize; ++i) {
        for(j = 1; j <= target; ++j) {
            // 若当前背包重量j小于nums[i]，则其值等于只考虑0到i-1物品时的值
            if(j < nums[i])
                dp[i][j] = dp[i - 1][j];
            // 否则，背包重量等于在背包中放入num[i]/不放入nums[i]的较大值
            else
                dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j  - nums[i]] + nums[i]);
        }
    }
    // 判断背包重量为target，且考虑到所有物品时，放入的元素和是否等于target
    return dp[numsSize - 1][target] == target;
}

一维数组AC代码：

/**
1. dp数组含义：dp[j]为背包重量为j时，其中可放入元素的最大值
2. 递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
3. 初始化：均初始化为0即可
4. 遍历顺序：先遍历物品，再后序遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

    int i;
    for(i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;
    // 背包容量
    int target = sum / 2;

    // 初始化dp数组，元素均为0
    int dp[target + 1];
    memset(dp, 0, sizeof(int) * (target + 1));

    int i, j;
    // 先遍历物品，后遍历背包
    for(i = 0; i < numsSize; ++i) {
        for(j = target; j >= nums[i]; --j) {
            dp[j] = MAX(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    
    // 查看背包容量为target时，元素总和是否等于target
    return dp[target] == target;
}