Frank's blogs

永远好奇

0%

背包问题（动态规划）

发表于 更新于
本文字数： 6.8k 阅读时长 ≈ 12 分钟

Leetcode 416. 分割等和子集

  • 背包原理教程
  • 此题实际上就是使用数组的元素作为物品，数组元素本身的大小就是价值，讨论是否能使用数组中的元素凑出数组大小一半的值
  • 使用的是01背包，倒序遍历即可
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n = nums.size();
            if (n < 2) {
                return false;
            }
            int sum = 0, maxNum = 0;
            for (auto& num : nums) {
                sum += num;
                maxNum = max(maxNum, num);
            }
            if (sum & 1) {
                return false;
            }
            int target = sum / 2;
            if (maxNum > target) {
                return false;
            }
            vector<bool> dp(target + 1, 0);
            dp[0] = true;
            for (auto& num : nums) {
                // int num = nums[i];
                for (int j = target; j >= num; --j) {
                    dp[j] = dp[j]|dp[j - num];
                }
            }
            return dp[target];
        }
    };

Leetcode 1049. 最后一块石头重量 II

  • 主要思路还是背包问题，只不过此时的背包容量和装的物品的价值都是石头的重量
  • 注意内存循环必须从后往前遍历，否则会导致前面被添加过的物品被连续重复添加
  • 外层循环的意思是使用到的石头是0-i个，内层的意思是石头总重不超过某个值的时候的最大总重是多少
    class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) 
        {
            int sum = 0;
            for(auto& i:stones)sum+=i;
            int target = sum/2;
            vector<int> maxArr(target+1, 0);

            for(int i = 0; i<stones.size(); ++i)
            {
                int wi = stones[i];
                for(int j = target; j>=wi; --j)
                {
                    maxArr[j] = max(maxArr[j], maxArr[j-wi]+wi);
                }
            }
            return sum - (maxArr[target]*2);
        }
    };

139. 单词拆分

  • 此题主要是将字符串视为一个背包，字典中的每个单词都是一个物品
  • 从字符串的每个位置开始，如果这个位置已经可达，那么从这个位置开始枚举substring，如果这个substring在字典中，则这个substring的位置也可达，从前往后遍历（因为每个单词使用次数不限制）
    class Solution {
    public:
        unordered_set<string> us; 
        vector<int> able;
        bool wordBreak(string s, vector<string>& wordDict) {
            vector<bool> able(s.size()+1, false);
            unordered_set<string> um;
            for(auto& w : wordDict)
            {
                um.insert(w);
            }
            able[0] = true;
            for(int i = 1; i<=s.size(); ++i)
            {
                if(!able[i-1])continue;
                for(int j = 1; i+j-1<=s.size(); ++j)
                {
                    if(um.count(s.substr(i-1, j)))
                    {
                        able[i+j-1] = able[i+j-1]|able[i-1];
                    }
                }
            }
            return able[s.size()];
        }
    };

Leetcode 474. 一和零

  • 此题是一个递推问题，做题方式类似于背包法
  • 遍历同样是外层循环指定此时能使用的字符串的最大index
  • 内层循环从已经可达的位置往外递推，类似于广度优先搜索
    class Solution {
    public:
        // int maxLen;
        vector<vector<vector<int>>> lenMap;
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<pair<int, int>> arr;
            for(auto& i: strs)
            {
                int c0 = 0, c1 = 0;
                for(auto& a:i)
                {
                    if(a == '0')++c0;
                    else ++c1;
                }
                arr.push_back(pair<int, int>(c0, c1));
            }

            vector<vector<int>> map(m+1, vector<int>(n+1, -1));
            map[0][0] = 0;
            for(int i = 0; i<arr.size(); ++i)
            {
                int c0 = arr[i].first;
                int c1 = arr[i].second;
                // int s = q.size();
                for(int j = m; j>=c0; --j)
                {
                    for(int k = n; k>=c1; --k)
                    {
                        if(map[j-c0][k-c1]<0)continue;
                        map[j][k] = max(map[j-c0][k-c1]+1, map[j][k]);
                        map[m][n] = max(map[m][n], map[j][k]);
                    }
                }
            }
            return map[m][n]<0?0:map[m][n];
        }
    };

    Leetcode 518. 零钱兑换II

  • 此题是一个完全背包类型的题参考链接
  • 注意循环次序的变化，0 1背包循环一般内层递推循环都是倒序的，但是这种是正序的
  • 完全背包遍历背包容量的时候是正序的，但是不完全背包遍历背包容量是倒序的
    class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            vector<int> arr(amount+1, 0);
            arr[0] = 1;
            // queue<int> q;
            // q.push(0);
            for(int i = 0; i<coins.size(); ++i)
            {
                for(int j = coins[i]; j<=amount; ++j)
                {
                    arr[j]+=arr[j-coins[i]];
                }
            }
            return arr[amount];
        }
    };

    Leetcode 377. 组合总和IV

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            vector<unsigned long> arr(target+1, 0);
            arr[0] = 1;
            for(int j = 0; j<=target; ++j)
            {
                for(auto &i : nums)
                {
                    if(j-i>=0)
                    arr[j]+=arr[j-i];
                }
            }
            return arr[target];
        }
    };

Leetcode 279. 完全平方数

  • 转化为一个完全背包问题即可
    class Solution {
    public:
        vector<int> minCnt;
        int numSquares(int n) {
            if(n == 0)return 0;
            else if(n == 1)return 1;

            minCnt = vector<int>(n+1, INT_MAX);
            minCnt[0] = 0;
            vector<int> nums;
            for(int i = 1; i*i<=n; ++i)
            {
                nums.push_back(i*i);
            }
            for(auto& i : nums)
            {
                for(int j = i; j<=n; ++j)
                {
                    if(minCnt[j-i]!=INT_MAX)minCnt[j] = min(minCnt[j], minCnt[j-i]+1);
                }
            }
            return minCnt[n];
        }

    };

卡码网 28. 子序列中的 k 种字母

  • 链接
  • 此题是一个背包问题，主要是先统计字符串中26个字母每个包含几个
  • 因为顺序无所谓，因此直接开始找字母的种类
  • 假设此时字符串已经有了k种字母，凑到k+1种字母的方式就是通过添加一个新的种类的字母，但是新的种类的字母可能有多个备选项比如n
  • 那么最终的字符串中可以在这n的字母种选择小于等于n的任意个，选择方式共有picture 0 种，上述结果的求和是2^n-1
  • 因此实际上在递推背包的时候，假如当前选择的字母的个数有n个，那么具有k种字母的字符串的种类是具有k-1种字母的字符串的种类*2^n-1
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;


int main()
{
    int n, k;
    cin>>n>>k;
    if(n<k)
    {
        cout<<0<<endl;
        return 0;
    }
    map<char, int> letters;
    char tmp;
    for(int i = 0; i<n; ++i)
    {
        cin >> tmp;
        letters[tmp]++;
    }
    vector<long long> combs(k+1, 0);
    combs[0] = 1;
    for(auto&i : letters)
    {
        long long sec = (long long)(pow(2, i.second)-1)%1000000007;
        for(int j = k; j>=1; --j)
        {
            combs[j]+=combs[j-1]*sec;
            combs[j]%=1000000007;
        }
    }

    cout<<combs[k]%1000000007<<endl;
}

nowcoder HJ16 购物单

  • 链接
  • 此题是一个分组背包问题，也就是每一组的物品只能买一个
  • 主要是在遍历每一组的不同物品尝试的时候，不能修改本身的dp数组，要遍历完某一个分组之后再修改
  • 此题因为一个物品最多有2个附属物品，因此每一组最多也就是4种组合，可以直接枚举
    #include <iostream>
    #include <sys/ucontext.h>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <cstdlib>

    using namespace std;

    int main() {
        int money, n;
        cin>>money>>n;
        vector<vector<vector<int>>> items(n);
        int a, b, c;
        for(int i = 0; i<n; ++i)
        {
            cin>>a>>b>>c;
            if(c == 0)
            {
                items[i].insert(items[i].begin(), {a, b, a*b});
            }
            else
            {
                items[c-1].push_back({a, b, a*b});
            }
        }
        for(int i = 0; i<n; ++i)
        {
            if(items[i].size() ==1)continue;
            else if(items[i].size() == 2)
            {
                items[i][1][0] += items[i][0][0];
                items[i][1][1] += items[i][0][1];
                items[i][1][2] += items[i][0][2];
           }
           else if(items[i].size() == 3)
           {
                items[i].push_back({items[i][0][0]+items[i][1][0]+items[i][2][0], items[i][0][1]+items[i][1][1]+items[i][2][1], items[i][0][2]+items[i][1][2]+items[i][2][2]});
                items[i][1][0] = items[i][0][0]+items[i][1][0];
                items[i][1][1] = items[i][0][1]+items[i][1][1];
                items[i][1][2] = items[i][0][2]+items[i][1][2];

                items[i][2][0] = items[i][0][0]+items[i][2][0];
                items[i][2][1] = items[i][0][1]+items[i][2][1];
                items[i][2][2] = items[i][0][2]+items[i][2][2];
           }
        }
        vector<int> dp(money+1, 0);
        for(int i = 0; i<n; ++i)
        {
            vector<int> dpRes = dp;
            for(int j = items[i].size()-1; j>=0; --j)
            {
                vector<int> dpTmp = dp;
                for(int k = money; k>=items[i][j][0]; --k)
                {
                    dpTmp[k] = max(dpTmp[k], dpTmp[k-items[i][j][0]]+items[i][j][2]);
                }
                for(int b = 0; b<dp.size(); ++b)
                {
                    dpRes[b] = max(dpTmp[b], dpRes[b]);
                }
            }
            dp = dpRes;
        }
        cout<<dp[money];
    }
    // 64 位输出请用 printf("%lld")

    494. 目标和

  • 此题不能用传统的背包理论做，因为是每个物品必须用到而不是可用可不用
  • 使用了两个数组滚动进行更新，从上一次迭代能达到的位置出发，推算这一次迭代能达到的位置以及能达到的方式
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            unordered_map<int, int> arr;
            int maxAbs = 0;
            for(auto i : nums)
            {
                maxAbs+=i;
            }
            arr[0] = 1;
            unordered_map<int, int> tmp;
            for(int i = 0; i<nums.size(); ++i)
            {
                int n = nums[i];
                tmp.clear();
                for(auto p : arr)
                {
                    tmp[p.first+n]+=p.second;
                    tmp[p.first-n]+=p.second;
                }
                arr = tmp;
            }
            
            return arr[target];
        }

        
    };