背包问题—动态规划

01背包问题：没有物品（元素）只能选择1次

【模板】01背包_牛客题霸_牛客网 (nowcoder.com)

#include <array>
#include <cstring>
#include <iostream>
#include<vector>
using namespace std;
int n,V;
int dp[1001][1001];

int main() {
    cin>>n>>V;
    vector<int> volume(n,0);
    vector<int> value(n,0);
    for(int i=0;i<n;i++){
        cin>>volume[i];
        cin>>value[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=V;j++){//j从0开始，要满足后面的填表
            dp[i][j]=dp[i-1][j];
            if(j-volume[i-1]>=0)//j-volume[i]==0：表示只用i这个就装满背包
            dp[i][j]=max(dp[i][j],dp[i-1][j-volume[i-1]]+value[i-1]);
        }
    }
    cout<<dp[n][V]<<endl;
    memset(dp, 0, sizeof(dp));
    //用-1表示不可能恰好装满的状态
    for(int i=1;i<=V;i++) dp[0][i]=-1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if(j-volume[i-1]>=0&&dp[i-1][j-volume[i-1]]!=-1)
                dp[i][j]=max(dp[i][j],dp[i-1][j-volume[i-1]]+value[i-1]);
        }
    }
    cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
}   

// 64 位输出请用 printf("%lld")

416. 分割等和子集 - 力扣（LeetCode）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int volume=sum/2;
        vector<vector<bool>> dp(n+1,vector<bool>(volume+1,false));
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=volume;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1])
                dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][volume];
    }   
};

494. 目标和 - 力扣（LeetCode）

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0; int n=nums.size();
        for(int i=0;i<n;i++){
            sum+=nums[i];
        } 
        int _target=(sum+target)/2;
        if(_target<0||(sum+target)%2==1) return 0;//_target<0,没有情况
        vector<vector<int>> dp(n+1,vector<int>(_target+1,0));//状态表示，在1~i中选择元素,1<=i<=n，一共有多少种选择可以达到_target
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=_target;j++){
                dp[i][j]=dp[i-1][j];
                if(j-nums[i-1]>=0){//法则2，下标有算法实际操作的数映射正确
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][_target];
    }
};

1049. 最后一块石头的重量 II - 力扣（LeetCode）

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size(); int sum=0;
        for(int &val:stones){
            sum+=val;
        }
        int aim=sum/2;
        vector<vector<int>> dp(n+1,vector<int>(aim+1,0));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=aim;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=stones[i-1]){
                    dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        return sum-2*dp[n][aim];
    }
};

完全背包，物品(元素)个数有无限个 

【模板】完全背包_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include <iterator>
#include <new>
using namespace std;
#include <vector>
int main() {
    int n,V;
    cin>>n>>V;
    vector<int> volume(n+1,0);
    vector<int> value(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>volume[i]>>value[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(V+1,0));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=volume[i]){
                dp[i][j]=max(dp[i-1][j],dp[i][j-volume[i]]+value[i]);
            }
        }
    }
    cout<<dp[n][V]<<endl;
    dp[0][0]=0;
    for(int i=1;i<=V;i++) dp[0][i]=-1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=volume[i]&&dp[i][j-volume[i]]!=-1){
                dp[i][j]=max(dp[i-1][j],dp[i][j-volume[i]]+value[i]);
            }
        }
    }
    cout<<(dp[n][V]==-1?0:dp[n][V]);

    return 0;
}
// 64 位输出请用 printf("%lld")

322. 零钱兑换 - 力扣（LeetCode）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1));
        dp[0][0]=0;
        for(int i=1;i<=amount;i++) dp[0][i]=-1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=coins[i-1]&&dp[i][j-coins[i-1]]!=-1){
                    if(dp[i-1][j]!=-1){
                        dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                    }else{
                        dp[i][j]=dp[i][j-coins[i-1]]+1;
                    }
                }
            }
        }
        return dp[n][amount];
    }
};

518. 零钱兑换 II - 力扣（LeetCode）

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1,0));
        dp[0][0]=1; 
        for(int i=1;i<=amount;i++) dp[0][i]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=coins[i-1])
                dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
};

279. 完全平方数 - 力扣（LeetCode）

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        dp[0]=0;  dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+1;
            for(int j=2;j*j<=i;j++){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }    
        }
        return dp[n];
    }
};

474. 一和零 - 力扣（LeetCode）

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len=strs.size();//优化
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=len;i++){
            for(int j=m;j>=0;j--){
                for(int k=n;k>=0;k--){
                    int size_0=0; int size_1=0;
                    for(char &ch:strs[i-1]){
                        if(ch=='0') size_0+=1;
                        else if(ch=='1') size_1+=1;
                    }
                    if(j>=size_0&&k>=size_1){
                        dp[j][k]=max(dp[j][k],dp[j-size_0][k-size_1]+1);//优化前，从小到大的话，一层状态转移从下标小的开始，如果要优化，使用滚动数组的话吗，必须从下标大的开始(二维数组的右下角)，否则状态可能从同次转移。
                    }
                }
            }
        }
        return dp[m][n];
    }
};


// class Solution {
// public:
//     int findMaxForm(vector<string>& strs, int m, int n) {
//         int len=strs.size();
//         vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));  
//         for(int i=1;i<=len;i++){
//             for(int j=0;j<=m;j++){
//                 for(int k=0;k<=n;k++){
//                     dp[i][j][k]=dp[i-1][j][k];
//                     int size_0=0; int size_1=0;
//                     for(char &ch:strs[i-1]){
//                         if(ch=='0') size_0+=1;
//                         else if(ch=='1') size_1+=1;
//                     }
//                     if(j>=size_0&&k>=size_1){
//                         dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-size_0][k-size_1]+1);
//                     }
//                 }
//             }
//         }
//         return dp[len][m][n];
        
//     }
// };

879. 盈利计划 - 力扣（LeetCode）

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int m=group.size();
        const int MOD=1e9+7;
        vector<vector<vector<int>>> dp(m+1,vector<vector<int>>(n+1,vector<int>(minProfit+1,0)));
        for(int j=0;j<=n;j++){
            dp[0][j][0]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                for(int k=0;k<=minProfit;k++){
                    dp[i][j][k]=dp[i-1][j][k];
                    if(j>=group[i-1]){//&&k>=profit[i-1],利润不用处理,因为profit[i-1]>k,表示利润高，这种情况可以取
                        dp[i][j][k]+=dp[i-1][j-group[i-1]][max(0,k-profit[i-1])];
                        dp[i][j][k]=dp[i][j][k]%MOD;
                    }
                }
            }
        }
        return dp[m][n][minProfit];
        
    }
};

377. 组合总和 Ⅳ - 力扣（LeetCode）

与找521 零钱兑换的方式的区别，这个是排列，顺序不同，也统计次数。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n=nums.size();
        vector<double> dp(target+1,0);
        //求target==0的排列。
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int &x:nums){
                if(x<=i)
                dp[i]+=dp[i-x];
            }
        }
        return dp[target];
    }
};

96. 不同的二叉搜索树 - 力扣（LeetCode）

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                dp[i]+=dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/697829.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

OJ刷题——2086.AI=？、2087.剪花布条、KPM算法

OJ刷题——2086.AI=？、2087.剪花布条、KPM算法

2086.AI&#xff1f; 题目描述 Problem - 2086 运行代码 #include <iostream> #include <cstdio> using namespace std; const int N 3005; int main() {int n;double Ao, An;double num[N];while (cin>>n) {cin >> Ao>>An;for (int i 1; i…
阅读更多...
MATLAB基础应用精讲-【数模应用】二元Logit分析

MATLAB基础应用精讲-【数模应用】二元Logit分析

目录 算法原理 数学模型 极大似然法 Newton牛顿迭代法 logit回归分析步骤 一、二元logit分析 1.基本说明 2.数据处理 3.SPSSAU上传数据 4.分析前提示 5.SPSSAU分析 6.其它说明 二、多分类logit分析 1.基本说明 2.数据要求与处理 3.SPSSAU上传数据 4.SPSSAU分析…
阅读更多...
C语言：结构体数组

C语言：结构体数组

结构体数组 介绍定义结构体定义结构体数组初始化结构体数组访问和修改结构体数组的元素遍历结构体数组 示例高级用法动态分配结构体数组使用 malloc 动态分配使用 calloc 动态分配 结构体数组作为函数参数结构体数组与指针多维结构体数组使用 typedef 简化结构体定义结构体数组…
阅读更多...
【文档智能 RAG】RAG增强之路：增强PDF解析并结构化技术路线方案及思路

【文档智能 RAG】RAG增强之路：增强PDF解析并结构化技术路线方案及思路

前言 现阶段&#xff0c;尽管大模型在生成式问答上取得了很大的成功&#xff0c;但由于大部分的数据都是私有数据&#xff0c;大模型的训练及微调成本非常高&#xff0c;RAG的方式逐渐成为落地应用的一种重要的选择方式。然而&#xff0c;如何准确的对文档进行划分chunks&…
阅读更多...
【Oracle生产运维】数据库服务器负载过高异常排查处理

【Oracle生产运维】数据库服务器负载过高异常排查处理

说明 在Oracle数据库运维工作中&#xff0c;经常会遇到Oracle数据库服务器平均负载&#xff08;load average&#xff09;突然异常升高&#xff0c;如果放任不管&#xff0c;严重的情况下会出现数据库宕机、服务器重启等重大故障。因此&#xff0c;当发现数据库服务器平均负载…
阅读更多...
shell编程（三）—— 控制语句

shell编程（三）—— 控制语句

程序的运行除了顺序运行外&#xff0c;还可以通过控制语句来改变执行顺序。本文介绍bash的控制语句用法。 一、条件语句 Bash 中的条件语句让我们可以决定一个操作是否被执行。结果取决于一个包在[[ ]]里的表达式。 bash中的检测命令由[[]]包起来&#xff0c;用于检测一个条…
阅读更多...
「网络原理」三次握手四次挥手

「网络原理」三次握手四次挥手

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;计网 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 三次握手&四次挥手 &#x1f349;连接管理&#x1f34c;三次握手&#x1f34c;意义&#x1f34c;四次挥手&#x1f34c;TCP 状态转换…
阅读更多...
目标检测算法YOLOv9简介

目标检测算法YOLOv9简介

YOLOv9由Chien-Yao Wang等人于2024年提出&#xff0c;论文名为&#xff1a;《YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information》&#xff0c;论文见&#xff1a;https://arxiv.org/pdf/2402.13616 &#xff1b;源码见: https://github.com/W…
阅读更多...
Hexo+Github搭建个人博客教程

Hexo+Github搭建个人博客教程

hexo官网&#xff1a;https://hexo.io/zh-cn/ butterfly 主题设置&#xff1a;https://butterfly.js.org/ GitHub地址&#xff1a;https://github.com/jerryc127/hexo-theme-butterfly 基础命令 初始化博客命令&#xff1a;hexo init “文件名” 开启本地服务&#xff08;本…
阅读更多...
linux centos consul1.15.2一键安装部署

linux centos consul1.15.2一键安装部署

consul原理、作用、安装相关内容 一、理论部分二、安装下载版本地址三、安装consul服务 一、理论部分 1、consul的原理 Consul的原理及作用可以归纳为以下几点&#xff1a; ①、基于Gossip协议的通信&#xff1a;Consul使用了基于Gossip协议的Serf实现来进行通信。 Gossip协议…
阅读更多...
C语言 | Leetcode C语言题解之第143题重排链表

C语言 | Leetcode C语言题解之第143题重排链表

题目&#xff1a; 题解&#xff1a; struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast->next ! NULL && fast->next->next ! NULL) {slow slow->next;fast fast->next-&g…
阅读更多...
Python酷库之旅-开启库房之门

Python酷库之旅-开启库房之门

目录 一、库的定义 二、库的组成 三、库的分类 四、如何学好Python库&#xff1f; 五、注意事项 六、推荐阅读 1、Python筑基之旅 2、Python函数之旅 3、Python算法之旅 4、Python魔法之旅 5、 博客个人主页 一、库的定义 在Python中&#xff0c;库(Library)是一个封…
阅读更多...
两台电脑通过网线直连共享数据（超详细）- 我的实践记录

两台电脑通过网线直连共享数据（超详细）- 我的实践记录

原文链接 按照原文的操作&#xff0c;成功通过直连网线连接了两台windows电脑并共享传输数据。 ping不通可能是防火墙没关闭导致的&#xff0c;但是完全关闭防火墙又不安全。 那么有没有不关闭防火墙&#xff0c;能够上网&#xff0c;又能直连另一台电脑呢&#xff1f; 我们…
阅读更多...
javaweb请求响应+@ResponseBody注解

javaweb请求响应+@ResponseBody注解

这里用了一款接口测试软件postman 简单参数 SpringBoot方式 简单参数:参数名与形参变量名相同&#xff0c;定义形参即可接收参数。 请求参数名与方法形参变量名相同 会自动进行类型转换 package com.example.springbootwebreqresp.Controller;import org.springframework.w…
阅读更多...
SSM框架超详细讲解

SSM框架超详细讲解

介绍SSM框架 一、什么是SSM框架&#xff1f; SSM框架是spring、spring MVC 、和mybatis框架的整合&#xff0c;是标准的MVC模式。标准的SSM框架有四层&#xff0c;分别是dao层&#xff08;mapper&#xff09;&#xff0c;service层&#xff0c;controller层和View层。使用spr…
阅读更多...
下拉框数据被遮挡 且 后续数据无法下拉的 解决方法

下拉框数据被遮挡 且 后续数据无法下拉的 解决方法

目录 前言1. 问题所示2. 原理分析3. 解决方法3.1 添加空白版2.2 调整z-index2.3 父容器的溢出属性2.4 调整样式属性4. 效果图前言 小程序使用的是Uniapp，原理都差不多，索性标题就不标注Uniapp（小程序） 对于该问题调试了一个晚上，最终解决，对此记录下来 1. 问题所示 执…
阅读更多...
Python中的数据可视化：分组柱状图

Python中的数据可视化：分组柱状图

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 Python中的数据可视化&#xff1a; 分组柱状图 选择题 关于以下代码输出结果的说法中正确的是? import seaborn as sns import matplotlib.pyplot as plt import pandas as pd data…
阅读更多...
Vue2基础：.sync修饰符的使用，认识，作用，本质案例演示，实现父子之间的通信。

Vue2基础：.sync修饰符的使用，认识，作用，本质案例演示，实现父子之间的通信。

.sync的作用&#xff1a; 可以实现子组件与父组件数据的双向绑定&#xff0c;简化代码。 与v-model的不同点,prop属性名可以自定义&#xff0c;不要一定要用value. .sync的本质&#xff1a; 就是&#xff1a;属性名和update&#xff1a;属性名合写。 下面我们进行代码演示…
阅读更多...
Kimichat使用案例009：添加常用语（使用技巧）

Kimichat使用案例009：添加常用语（使用技巧）

文章目录 一、介绍二、常用语操作过程三、语言设置四、操作一、介绍 使用kimichat进行翻译，通常会使用提示语：翻译成中文。如果每天都要大量使用这一个功能，可以把提示语添加成常用语，直接点击调用即可，就不用再一次次重复输入了。 二、常用语操作过程 在kimichat的提示语…
阅读更多...
wordpress入门教程，wordpress快速入门，wordpress教程视频

wordpress入门教程，wordpress快速入门，wordpress教程视频

WordPress是一款广受欢迎的开源博客平台和内容管理系统&#xff0c;自2003年诞生以来&#xff0c;它不断发展和完善&#xff0c;如今已成为互联网上众多网站、博客的首选构建工具。 1、搜索“方圆资源网官网” WordPress教程的资源非常丰富&#xff0c;只要找到合适的途径&…
阅读更多...
最新文章

Copyright @ 2022~2023