算法【01背包】

01背包是背包问题中最基础最简单的类型，只是对每个物品要和不要两种可能性展开，不存在过多的困难。

下面通过几个题目加深理解。

题目一

测试链接：[NOIP2005 普及组] 采药 - 洛谷

分析：这个是01背包模板的题目。dp[i][j]表示，在前i个草药里面选，总共时间为j，可以采到的草药的最大总价值。对可能性的展开就是第i个草药选不选第i个草药有两种可能性，不选和选，比较它们的最大值。代码如下。

#include <iostream>
using namespace std;
int T;
int M;
int herb[100][2];
int dp[101][1001];
int main(void){
    scanf("%d%d", &T, &M);
    for(int i = 0;i < M; ++i){
        scanf("%d%d", &herb[i][0], &herb[i][1]);
    }
    for(int i = 0;i < 1000; ++i){
        dp[0][i] = 0;
    }
    for(int i = 0;i < 101; ++i){
        dp[i][0] = 0;
    }
    for(int i = 1;i <= M;++i){
        for(int j = 1;j <= T;++j){
            dp[i][j] = dp[i-1][j];
            if(j - herb[i-1][0] >= 0){
                dp[i][j] = dp[i][j] > dp[i-1][j-herb[i-1][0]] + herb[i-1][1] ?
                dp[i][j] : dp[i-1][j-herb[i-1][0]] + herb[i-1][1];
            }
        }
    }
    printf("%d", dp[M][T]);
    return 0;
}

进行空间压缩后的代码如下。

#include <iostream>
using namespace std;
int T;
int M;
int herb[100][2];
int dp[1001];
int main(void){
    scanf("%d%d", &T, &M);
    for(int i = 0;i < M; ++i){
        scanf("%d%d", &herb[i][0], &herb[i][1]);
    }
    for(int i = 0;i <= 1000; ++i){
        dp[i] = 0;
    }
    for(int i = 1;i <= M;++i){
        for(int j = T;j >= 0 && j >= herb[i-1][0];--j){ 
            dp[j] = dp[j] > dp[j-herb[i-1][0]] + herb[i-1][1] ?
            dp[j] : dp[j-herb[i-1][0]] + herb[i-1][1];
        }
    }
    printf("%d", dp[T]);
    return 0;
}

题目二

测试链接：bytedance-006. 夏季特惠 - 力扣（LeetCode）

分析：这道题需要进行一定的转化，才能使用01背包进行求解，可以看出，如果优惠大于现价，那么对于预算的影响就是增大预算，所以对于这种情况的商品是一定要购买的。那么，可以将所有的商品遍历一遍，找出一定要购买的商品，得到新的预算。对于不一定购买的商品，重新得到一个数据，在这个数据里面进行01背包，加上一定购买商品的快乐值，即是尽可能多的快乐值。代码如下。

#include <iostream>
using namespace std;
int n, X;
int game[500][2];
int dp[100000];
int main(void){
    int index = 0;
    int a_i, b_i, w_i;
    int happy = 0;
    scanf("%d%d", &n, &X);
    for(int i = 0;i < n;++i){
        scanf("%d%d%d", &a_i, &b_i, &w_i);
        if(a_i - b_i >= b_i){
            happy += w_i;
            X += (a_i - b_i - b_i);
        }else{
            game[index][0] = 2 * b_i - a_i;
            game[index++][1] = w_i;
        }
    }
    for(int i = 0;i <= X;++i){
        dp[i] = 0;
    }
    for(int i = 1;i <= index;++i){
        for(int j = X;j >= 0 && j - game[i-1][0] >= 0;--j){
            dp[j] = dp[j] > dp[j-game[i-1][0]] + game[i-1][1] ? 
            dp[j] : dp[j-game[i-1][0]] + game[i-1][1];
        }
    }
    printf("%d", happy+dp[X]);
    return 0;
}

题目三

测试链接：494. 目标和 - 力扣（LeetCode）

分析：对于这道题，将数分为了正数和负数两个部分，那么可以列出两个等式，正数部分-负数部分=总和，正数部分+负数部分=target，那么即可得到正数部分的和。如果正数部分的和不为整数或者为负数则返回0。这样就形成了一个01背包dp[i][j]表示在前i个数里面选和为j的选择方法的数目有多少种。可能性的展开也是有两种，对于第i个数选或是不选，但这里不是求最大值，求完dp表后即可得到答案。代码如下。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int dp[1001];
        int sum = 0;
        int length = nums.size();
        for(int i = 0;i < length;++i){
            sum += nums[i];
        }
        if(((target + sum) & 1) == 1){
            return 0;
        }
        int pos = (sum + target) / 2;
        if(pos < 0){
            return 0;
        }
        for(int i = 0;i <= pos;++i){
            dp[i] = 0;
        }
        dp[0] = 1;
        for(int i = 1;i <= length;++i){
            for(int j = pos;j >= 0;--j){
                if(j - nums[i-1] >= 0){
                    dp[j] += dp[j-nums[i-1]];
                }
            }
        }
        return dp[pos];
    }
};

题目四

测试链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

分析：这道题可以将石头总重量平均分为两个部分，对较小部分进行01背包填充得到最大填充重量，这样就将石头分为了两个部分，一个是填充的部分，一个是未填充的部分，这两个部分进行碰撞，剩下的即是最小重量。代码如下。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        int dp[1501];
        int length = stones.size();
        for(int i = 0;i < length;++i){
            sum += stones[i];
        }
        int small = sum / 2;
        for(int i = 0;i <= small;++i){
            dp[i] = 0;
        }
        for(int i = 1;i <= length;++i){
            for(int j = small;j >= 0 && j - stones[i-1] >= 0;--j){
                dp[j] = dp[j] > dp[j-stones[i-1]] + stones[i-1] ? 
                dp[j] : dp[j-stones[i-1]] + stones[i-1];
            }
        }
        return sum - 2 * dp[small];
    }
};