动态规划算法4

卡码网 46 携带研究材料 2023.12.6

• 题目链接
• 常规二维dp数组方法代码随想录讲解[链接]
• 一维滚动数组方法代码随想录讲解[链接]
  

//二维dp数组做法
#include<bits/stdc++.h>
using namespace std;

int main()
{
    //m为材料种类数，n为行李箱最大空间数
    int m, n;
    cin >> m >> n;
    //room数组存储m种材料所占的体积
    vector<int> room(m, 0);
    for(int i = 0; i < m; i++)
        cin >> room[i];
    //value数组存储m种材料所占的价值
    vector<int> value(m, 0);
    for(int i = 0; i < m; i++)
        cin >> value[i];
    //1确定动态规划dp数组及其下标含义，这里指第(1, m)种材料(对应索引0，m-1)在占用(0, n)体积时的价值
    vector<vector<int>> dp(m, vector<int>(n+1, 0));
    //3初始化，存储第一种材料的价值，背包体积大于room[0]时，背包的价值为value[0]
    //下面是两种初始化方法
    for(int i = room[0]; i <= n; i++)
    {
        dp[0][i] = value[0];
    }
    // for(int i = 1; i < n; i++)
    // {
    //     if(room[0] <= i)
    //         dp[0][i] = value[0];
    // }
    //2确定递推公式 4 确定递推遍历顺序
    for(int i = 1; i < m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            //当背包体积不够时，不装第i种材料，此时最大价值为dp[i-1][j]背包的价值
            if(room[i] > j)
                dp[i][j] = dp[i-1][j];
            //当背包体积够时，取价值最大值，不装第i种材料的价值，装第i种材料的价值+背包剩余体积装材料的最大价值
            else
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-room[i]]+value[i]);
        }
    }
    //dp[m-1][n]表示m种材料装在n体积背包的最大价值
    cout << dp[m-1][n] << endl;
    return 0;
}

//一维dp数组做法(滚动数组)
#include<bits/stdc++.h>
using namespace std;

int main()
{
    //m为材料种类数，n为行李箱最大空间数
    int m, n;
    cin >> m >> n;
    //room数组存储m种材料所占的体积
    vector<int> room(m, 0);
    for(int i = 0; i < m; i++)
        cin >> room[i];
    //value数组存储m种材料所占的价值
    vector<int> value(m, 0);
    for(int i = 0; i < m; i++)
        cin >> value[i];
    //1确定动态规划dp数组及其下标含义，这里指占用[0, n]体积时的价值
    vector<int> dp(n+1, 0);
    //3初始化，存储第一种材料的价值，背包体积大于room[0]时，背包的价值为value[0]
    //2确定递推公式 4 确定递推遍历顺序
    //遍历m种材料
    for(int i = 0; i < m; i++)
    {
        //倒序遍历[room[i], j]体积下的最大价值
        //不能用正序遍历，否则dp[2]会重复dp[1]
        for(int j = n; j >= room[i]; j--)
        {
            //递推公式，取两者最大值
            //dp[j]（前面遍历的该体积下的最大价值），
            //dp[j-room[i]]+value[i],j-room[j]空间大小下的最大价值+第i种材料的价值
            dp[j] = max(dp[j], dp[j-room[i]]+value[i]);
        }
    }
    //dp[n]表示n体积背包的最大价值
    cout << dp[n] << endl;
    return 0;
}

---

LeetCode 416 分割等和数组 2023.12.6

• 题目链接
• 代码随想录讲解[链接]
  

bool canPartition(vector<int>& nums) {
    //sum存储nums数组的总和
    int sum = 0;
    // for (int i = 0; i < nums.size(); i++)
    //     sum += nums[i];
    //求和或拼接函数(迭代器，迭代器，累加值i)，sum=数组和+i
    sum = accumulate(nums.begin(), nums.end(), 0);
    cout << sum << endl;
    //先判断和是否为偶数，如果不是则不能分为两个等和数组，直接返回false
    if(sum%2 == 1)
        return false;
    //和为偶数时，两个等和数组的和目标值为一半和
    int target = sum/2;
    //1确定dp数组，其下标含义为当前背包下的最大子数组和，3初始化元素都为0
    //因为数组元素最大值100，数组大小最大为100，那么最大target为10000
    vector<int> dp(10001, 0);
    //2确定递推公式，4确定遍历顺序，数组中每个元素只使用一次，那么倒序遍历
    for (int i = 0; i < nums.size(); i++)
    {
	    //j为背包的大小，需要大于当前遍历值
        for(int j = target; j >= nums[i]; j--)
            //取极大值：判断之前遍历的元素在背包j值时的最大元素和与加入该值后的最大元素和
            dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
    }
    //最终判断条件，在能存储数值为target的背包内值为target时，说明能分为两个等和数组
    if(dp[target] == target)
        return true;
    return false;
}

---

LeetCode 1049 最后一块石头的重量-ii 2023.12.6

• 题目链接
• 代码随想录讲解[链接]
  

int lastStoneWeightII(vector<int>& stones) {
    //sum存储石头总重量
    int sum = accumulate(stones.begin(), stones.end(), 0);
    //target存储一半石头总重量，当总重量为奇数时，2*target<sum
    int target = sum/2;
    //1确定dp数组，其下标含义为能存储重量为i的背包最大能存储石头重量
    //本题中想把石头分为重量相同或者相近的两堆，这样最后剩下的石头重量为0或者最小
    //3初始化元素均为0
    vector<int> dp(target+1, 0);
    //2确定递推公式，4确定遍历顺序
    //计算重量为i的背包最大能存储石头重量，每块石头只能用一次所以倒序遍历
    for (int i = 0; i < stones.size(); i++)
    {
        //j为背包的大小，需要大于当前遍历重量值
        for(int j = target; j >= stones[i]; j--)
            //取极大值：判断之前遍历的元素在背包j值时的最大重量和与加入该重量值后的最大重量和
            dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
    }
    //能存储target一半总重量的背包最多能存储target重量或者更少
    //sum-dp[target]为另一堆更多的重量，减掉dp[target]即为最小重量；相同时答案为0
    return sum - dp[target] - dp[target];
}

---