背包问题：
01 背包
二维数组dp[i][j]解法
纯01背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
dp[i][j]:从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式：对于dp[i][j]来说，有两种方式得到一种时正上方，就时不放物品i,还有一种就是从左上方得来，就是放物品i
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化：dp[i][0] = 0,这里的意思是当重量为零的时候，无论选取哪些物品，背包总价值都是为零的，
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
其他的位置的话，其实初始什么数值都是可以的，因为dp[i][j]是由左上方和正上方决定的，其他的位置都是会被覆盖的，初始化成零的话，更方便一点
遍历顺序：
先遍历物品还是先遍历重量都一样
所以说当是dp二维数组时候，不管是遍历那个方向都可以
代码实现：
#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;
}memset 是 C 和 C++ 标准库中的一个函数，用于将内存区域的前 num 个字节设置为指定的值。它的原型通常在 <string.h> 或 <cstring> 头文件中定义。
函数的原型如下：
c复制代码
void *memset(void *s, int c, size_t n); |
参数解释：
-
s：指向要设置的内存区域的指针。 -
c：要设置的值。通常，这是一个整数，但会被强制转换为unsigned char，然后复制到目标内存的每个字节。 -
n：要设置的字节数。
函数返回指向 s 的指针。
一维数组（滚动数组）
一维数组就是将二维数组给压缩了， 将上一层的情况复制到下一层去（这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。）
dp[j] :容量为j的背包，所背的物品价值可以最大为dp[j]
递推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);这个其实就是二维数组没有i那个维度，dp[j]相当于的dp[i-1][j]这一层
初始化：
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
4遍历顺序：
背包容量是从大到小，就是倒序遍历
——这是为了保证物品i只被放入一次，因为正序遍历中，要进行减一操作，所以说会有一个物品被同时放入的情况
为什么二维数组中可以不用考虑遍历顺序？
——因为二维数组中每一层的数据是单独分开来的，而一维数组中是重复利用的，为了保证只放入一次，所以一维数组中要倒序
#include <stdio.h>
#include <string.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ARR_SIZE(arr) ((sizeof((arr))) / sizeof((arr)[0]))
#define BAG_WEIGHT 4
void test_back_pack(int* weights, int weightSize, int* values, int valueSize, int bagWeight) {
int dp[bagWeight + 1];
memset(dp, 0, sizeof(int) * (bagWeight + 1));
int i, j;
// 先遍历物品
for(i = 0; i < weightSize; ++i) {
// 后遍历重量。从后向前遍历
for(j = bagWeight; j >= weights[i]; --j) {
dp[j] = MAX(dp[j], dp[j - weights[i]] + values[i]);
}
}
// 打印最优结果
printf("%d\n", dp[bagWeight]);
}
int main(int argc, char** argv) {
int weights[] = {1, 3, 4};
int values[] = {15, 20, 30};
test_back_pack(weights, ARR_SIZE(weights), values, ARR_SIZE(values), BAG_WEIGHT);
return 0;
}416. 分割等和子集
这道题目可以抽象成一道背包问题，只不过是这时候物品的重量和价值都是子集本身
dp[j]:容量为j，最大值为dp[j]
递推公式：dp[j] = max(dp[j],dp[j-numsj] + nums[j)，
初始化：dp[0] = 0，题目中提到这个子集为正数的，所以不可能存在负数
其他应该初始化成什么？
——是初始成任意的数字嘛，因为递推公式中有比较的关系，假如初始化过大，可能导致正确的值无法被保存到，所以说要初始化到最小的值
遍历顺序：从后到前
#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;
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]);
}
}
return dp[target] == target;
}文章来源地址https://www.toymoban.com/news/detail-845299.html文章来源：https://www.toymoban.com/news/detail-845299.html
到了这里，关于代码随想录day42|背包问题、416. 分割等和子集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
