代码随想录算法训练营第三十四天|Day34 动态规划

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html

视频讲解：https://www.bilibili.com/video/BV1BU4y177kY

思路

#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int n, bagweight;
    scanf("%d %d", &n, &bagweight);
    int *weight = (int *)malloc(n * sizeof(int));
    int *value = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        scanf("%d", &weight[i]);
    }
    for (int j = 0; j < n; ++j) {
        scanf("%d", &value[j]);
    }
    int **dp = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; ++i) {
        dp[i] = (int *)malloc((bagweight + 1) * sizeof(int));
        for (int j = 0; j <= bagweight; ++j) {
            dp[i][j] = 0;
        }
    }
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= bagweight; j++) {
            if (j < weight[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    printf("%d\n", dp[n - 1][bagweight]);

    for (int i = 0; i < n; ++i) {
        free(dp[i]);
    }
    free(dp);
    free(weight);
    free(value);
    return 0;
}

学习反思

首先从输入中读取背包的最大容量和物品个数。然后使用动态内存分配创建weight和value数组来存储每个物品的重量和价值。接下来，创建一个二维数组dp来保存中间结果。dp[i][j]表示在前i个物品中选择，背包容量为j时的最大总价值。接着对dp数组进行初始化，将第一个物品的可选择重量范围内的dp值设置为对应的物品价值。然后，通过一个嵌套循环遍历每个物品和背包容量，计算dp[i][j]的值。如果当前背包容量j小于物品i的重量，说明物品i无法放入背包中，即dp[i][j]等于dp[i-1][j]；否则，比较不放入物品i和放入物品i的两种情况下的最大总价值，选取较大值作为dp[i][j]的值。最后，输出dp数组最后一个元素dp[n-1][bagweight]即为问题的解。

bool canPartition(int* nums, int numsSize) {
    int total = 0;
    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }
    if (total % 2 != 0) {
        return false;
    }
    int target = total / 2;
    bool dp[target + 1];
    for (int i = 0; i <= target; i++) {
        dp[i] = false;
    }
    dp[0] = true; 
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target]; 
}

学习反思

首先计算数组中所有元素的总和，如果总和为奇数，则无法分割成两个和相等的子集，直接返回false。然后，计算目标值target，即总和的一半。创建一个bool类型数组dp，大小为target+1，用来保存是否能够组成和为对应索引的子集。dp[i]为true表示能够组成和为i的子集，dp[i]为false表示不能组成和为i的子集。初始化dp数组，将所有元素初始化为false，然后将dp[0]设置为true，表示和为0的子集一定可以组成。接下来，使用两个嵌套循环遍历数组和目标值。对于每个元素nums[i]，从目标值target开始向前遍历，如果能够组成和为j - nums[i]的子集，即dp[j - nums[i]]为true，那么当前位置的dp[j]也设置为true。循环结束后，如果dp[target]为true，则表示数组可以分割为两个和相等的子集，返回true；否则返回false。

总结

动态规划，加油！！！