首页 > 其他分享 >(46/60)单词拆分、多重背包

(46/60)单词拆分、多重背包

时间:2024-03-21 23:58:01浏览次数:26  
标签:背包 weight 46 cin 60 int vector 拆分 dp

day46

单词拆分

leetcode:139. 单词拆分

动态规划

代码实现

/*
意义:长度为j的字符串能否被dict里的单词拼出为dp[j]
递推:if(dp[j] && j~i子串在dict里) dp[i] = true;
初始化:dp[0] = true 无意义,只是滚雪球起点;其余为false
遍历:对顺序有要求,排列数,先背包后物品;可重复取,正序
*/

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set wordSet(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size() + 1,false);
        dp[0] = true;
        for(int i = 1;i <= s.size();i++){
            for(int j = 0;j < i;j++){
                string word = s.substr(j,i-j);
                // cout<<word<<' ';
                if(wordSet.find(word) != wordSet.end() && dp[j]){
                    dp[i] = true;
                }
            }
            // cout<<endl;
        }

        return dp[s.size()];
    }
};

多重背包

卡码网:携带矿石资源(第八期模拟笔试)

动态规划

思路

多重背包就是把同类型的物品拆包出来,转化为0-1背包。

代码实现

/*
意义:dp[j]
*/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int C = 0;  // capacity
    int N = 0;  // types
    cin>>C;cin>>N;
    vector<int> weight(N,0);
    vector<int> value(N,0);
    vector<int> nums(N,0);
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < N;j++){
            if(i == 0)  cin>>weight[j];
            else if(i == 1) cin>>value[j];
            else if(i == 2) cin>>nums[j];
        }
    }
    
    // 有多个同类型的拆包
    for(int i = 0;i < N;i++){
        while(nums[i] > 1){
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }

    
    
    vector<int> dp(C+1,0);
    // 0-1背包。先物品再背包;倒序
    // 注意现在的物品数量应该是size()
    for(int i = 0;i < weight.size();i++){
        for(int j = C;j >= weight[i];j--){
            dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
        }
    }
    
    cout<<dp[C];
    
    
    return 0;
}

背包总结

img

标签:背包,weight,46,cin,60,int,vector,拆分,dp
From: https://www.cnblogs.com/tazdingo/p/18088506

相关文章

  • (45/60)爬楼梯进阶、零钱兑换、完全平方数
    day45爬楼梯进阶卡码网:爬楼梯(第八期模拟笔试)动态规划代码实现/*总和为j总共有dp[j]种方法(可重复选取、排列)dp[j]+=dp[j-nums[i]dp[0]=1;其余为0先背包再物品,正序*/#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){......
  • (44/60)完全背包、零钱兑换Ⅱ、组合总和Ⅳ
    day44完全背包卡码网:携带研究材料(第七期模拟笔试)动态规划思路完全背包,物品可以无限次取,正序遍历。复杂度分析时间复杂度:O(N^2)。空间复杂度:O(N)。代码实现#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;/*给j的容量可重复选择的最......
  • (51/60)买卖股票的最佳时机含冷冻期、买卖股票的最佳时机含手续费
    day51买卖股票的最佳时期含冷冻期leetcode:309.买卖股票的最佳时机含冷冻期动态规划代码实现/*意义:下标为i时各种情况的收益dp[i][0]持有dp[i][1]当天卖出dp[i][2]之前不持有递推:dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);//之前持有、之前不持有且当......
  • (50/60)买卖股票的最佳时机Ⅲ、买卖股票的最佳时机Ⅳ
    day50买卖股票的最佳时机Ⅲleetcode:123.买卖股票的最佳时机III动态规划代码实现/*意义:下标为i时,不同状态收益为dp[i][0]未持有dp[i][1]第一次持有dp[i][2]第一次未持有dp[i][3]第二次持有dp[i][4]第二次未持有递推:dp[i][0]=dp[i-1][0];之前未持有dp[i]......
  • (48/60)买卖股票的最佳时机、买卖股票的最佳时机Ⅱ
    day48买卖股票的最佳时机leetcode:121.买卖股票的最佳时机动态规划代码实现/*意义:dp[i][0]下标为i天持有股票的最大收益;dp[i][1]下标为i天不持股的最大收益递推:之前买入、当天买入:dp[i][0]=max(dp[i-1][0],-prices[i]);之前卖出、当天卖出:dp[i][1]=max(dp[i-1][1],......
  • (47/60)打家劫舍、打家劫舍Ⅱ、打家劫舍Ⅲ
    day47打家劫舍leetcode:198.打家劫舍动态规划代码实现/*偷到下标为i的最大金额数为dp[i]偷i、不偷i:dp[i]=max(dp[i-2]+nums[i],dp[i-1]);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);正序遍历*/classSolution{public:introb(vector<int>&nums){......
  • 科技赋能生活:KTH1601让垃圾桶“懂”你的需求
    在现代社会,科技的快速发展不仅仅改变了我们的生活方式,甚至连日常生活中的垃圾桶也变得“智能”起来。高性能、低功耗霍尔开关传感器KTH1601,正是让智能垃圾桶能够自动感应、自动开关的关键所在。它是由昆泰芯微电子科技有限公司研发的一款全极磁场检测传感器,具备非常低的功耗......
  • MT2492 16V输入 600KHz 2A DCDC同步降压转换器 航天民芯一级代理
    深圳市润泽芯电子有限公司为航天民芯一级代理描述  MT2492是一款完全集成的高效率产品2A同步整流降压变换器。MT2492在一段时间内高效运行宽输出电流负载范围。该设备提供两种工作模式,即PWM控制和PFM模式切换控制在更宽的工作范围内实现高效率加载。MT2492需要最少数量的......
  • 代码随想录算法训练营day29 | leetcode 491. 非递减子序列、46. 全排列、47. 全排列 I
    目录题目链接:491.非递减子序列-中等题目链接:46.全排列-中等题目链接:47.全排列II-中等题目链接:491.非递减子序列-中等题目描述:给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重......
  • 汽车用GMR角度传感器,TLE5014P16DXUMA1、TLE5014S16DXUMA1、TLE5014SP16DE0002XUMA1(360
    TLE5014GMR角度传感器有以下型号可供选择:TLE5014C16:汽车用GMR角度传感器,带SPC接口TLE5014P16:汽车用GMR角度传感器,带PWM接口TLE5014S16:汽车用GMR角度传感器,带SENT接口概述TLE5014基于巨磁阻(GMR)的角度传感器侧重于转向角传感器,设计用于汽车应用的角度位置检测。这些传感......