背包问题:
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;
}