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

发布时间:2023年12月20日

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

一、背包问题

题目:有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;
}

文章来源:https://blog.csdn.net/qq_57729144/article/details/135095871
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。