算法训练(leetcode)第三十天 | 46. 携带研究材料(第六期模拟笔试)、416. 分割等和子集

*46. 携带研究材料(第六期模拟笔试)

leetcode题目地址

01背包问题。使用dp算法。
二维数组dp[i][j]的含义:在背包容量为 j 的情况下,从物品 0-i 中任意取得物品的最大价值。
01背包中的每个物品有两种状态:取 或 不取。
因此,在dp[i][j]赋值时会有两种情况:

  • 不取第i个物品,则当前位置的最大价值等同于上一个物品位置在当前背包容量下的最大价值: d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i-1][j] dp[i][j]=dp[i1][j]
  • 取第i个物品,则当前位置的最大价值等同于上一个物品位置在背包容量刚好可以放下当前物品下的最大价值加上当前物品的价值: d p [ i ] [ j ] = d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] dp[i][j] = dp[i-1][j-weight[i]] + value[i] dp[i][j]=dp[i1][jweight[i]]+value[i]

这样就可以得出状态转移方程: d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) dp[i][j]=max(dp[i1][j],dp[i1][jweight[i]]+value[i])

在背包容量为0时,所有物品位置的价值都为0,因此,需要将dp[i][0]初始化为0。

二维数组

时间复杂度: O ( m ∗ n ) O(m * n) O(mn)
空间复杂度: O ( m ∗ n ) O(m * n) O(mn)

// c++
#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, n;
    cin>>m>>n;

    vector<int> weight(m,0);
    vector<int> value(m,0);

    for(int i=0; i<m; i++){
        cin>>weight[i];

    }
    for(int i=0; i<m; i++){
        cin>>value[i];
 
    } 
    vector<vector<int>> dp(m, vector<int>(n+1, 0));
    
    for(int j=weight[0]; j<=n; j++){
        dp[0][j] = value[0];
    }
    
    for(int i=1; i<m; i++){
        for(int j=1; j<=n; j++){
            if(weight[i]>j) dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
            }

        }

    }
    
    cout << dp[m-1][n] << endl;
    return 0;
}

一维数组(滚动数组)

使用滚动数组时,背包容量需要从后向前遍历,因为从前向后会导致同一个物品被重复加多次。

时间复杂度: O ( m ∗ n ) O(m * n) O(mn)
空间复杂度: O ( n ) O(n) O(n)

// c++
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int m, n;
    cin>>m>>n;
    // Files *files = new Files[m];
    vector<int> weight(m,0);
    vector<int> value(m,0);
    // int x;
    for(int i=0; i<m; i++){
        cin>>weight[i];
        // weight.emplace_back(x);  
    }
    for(int i=0; i<m; i++){
        cin>>value[i];
        // value.emplace_back(x);  
    } 
    vector<int> dp(n+1, 0);
     
    // for(int j=weight[0]; j<=n; j++){
    //     dp[0][j] = value[0];
    // }
     
    for(int i=0; i<m; i++){
        for(int j=n; j>=weight[i]; j--){
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i]);
            // cout<<dp[i][j]<<" ";
        }
        // cout<<endl;
    }
     
    cout << dp[n] << endl;
    return 0;
}

416. 分割等和子集

leetcode题目地址

依旧是01背包问题,使用上面的滚动数组方法来求解。

本题的主要思路是先将数组中的所有数求和,若该数组中的部分元素之和等于所有元素之和的一半则返回true。
因此数组元素之和必须是偶数才能等分,若是奇数直接返回false。
接下来就是经典的01背包求解了,nums中的元素同时作为weight和value进行求解。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

// c++
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
        }
        if(sum%2!=0) return false;
        int target = sum/2;

        vector<int> dp(target+1, 0);

        for(int i=0; i<nums.size(); i++){
            if(nums[i]==target) return true;
            for(int j=target; j>=nums[i]; j--){
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        
        if(dp[target]==target) return true;
        return false;

    }
};

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 02:16:03       106 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 02:16:03       116 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 02:16:03       95 阅读
  4. Python语言-面向对象

    2024-07-21 02:16:03       103 阅读

热门阅读

  1. 跨平台webSocket模块设计技术解决方案

    2024-07-21 02:16:03       29 阅读
  2. Angular之store全局状态管理 浅学

    2024-07-21 02:16:03       27 阅读
  3. 暗网与深网的技术原理、应用及社会影响探究

    2024-07-21 02:16:03       25 阅读
  4. Spring Cloud Gateway 响应数据加密

    2024-07-21 02:16:03       31 阅读
  5. HTTP爬虫IP流量和数量计费模式选择指南

    2024-07-21 02:16:03       30 阅读
  6. PHP项目开发流程概述

    2024-07-21 02:16:03       24 阅读
  7. Go知识点记录

    2024-07-21 02:16:03       28 阅读
  8. DAY05 CSS

    DAY05 CSS

    2024-07-21 02:16:03      28 阅读