算法设计与分析 动态规划/回溯

1.最大子段和

int a[N];
int maxn(int n)
{int temp=a[0];int ans=0;ans=max(temp,ans);for(int i=1;i<n;++i){if(temp>=0){temp+=a[i];}else	temp=a[i];ans=max(temp,ans);}return ans;
}
int main()
{int n,ans=0;cin>>n;for(int i=0;i<n;++i)	cin>>a[i];ans=maxn(n);cout<<ans;return 0;
}

2. 

int main()
{string a,b;cin>>a>>b;if(a.length()>b.length())	swap(a,b);int l1=a.length(),l2=b.length();int start=0,maxn=0;int dp[l2+1][l2+1];for(int i=0;i<l1;++i)	dp[i][0]=0;for(int j=0;j<l2;++j)	dp[0][j]=0;for(int i=1;i<=l1;++i){for(int j=1;j<=l2;++j){if(a[i-1]==b[j-1])	dp[i][j]=dp[i-1][j-1]+1;if(dp[i][j]>maxn){maxn=dp[i][j];start=i-maxn;}}}cout<<maxn<<" ans:"<<a.substr(start,maxn);return 0;
}

 3.

#include<iostream>
#include<stdio.h>
using namespace std;void Knapsack(int n,int c,int *w,int *p){int f[100][100];int i=0,j=0;for(i=1;i<=n;i++){for(j=1;j<=c;j++){f[i][j]=f[i-1][j];if(j>=w[i]){f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+p[i]);}}}cout<<"背包能装的最大价值是:" << f[i-1][j-1] <<endl;
}
int main(){int n;int c;int w[100]; int p[100];cout << "请输入背包容量c:"<< endl;cin >>c;cout <<"请输入物体个数n:"<<endl;cin >>n;for(int i=1;i<=n;i++) {cout<<"请输入物重w["<<i<<"]:"<<endl;cin >> w[i]; }for(int i=1;i<=n;i++) {cout<<"请输入物价p["<<i<<"]:"<<endl;cin >> p[i];}Knapsack(n,c,w,p);}

 4.

typedef struct{char name;float v;float w;float key;
}goods;
int n;vector<goods> g;
float nowweight=0;
float remainweight=10; 
float nowvalue=0;
vector<int> bagG;
float bestV=0;
vector<int> bestS; 
float shangjie=0;
void digui(int k) 
{int i,j=0,maxG;float shangjie=0;if(k>n) {if(nowvalue> bestV){for(int i=0;i<n;i++){bestS[i]=bagG[i];}bestV=nowvalue; } return; }maxG=remainweight/g[k].w;shangjie=nowvalue+(remainweight-nowweight)*g[k].key;if(bestV>=shangjie)return;for(i=maxG;i>=0;i--){if(nowweight+i*g[k].w <=remainweight ){nowweight += i*g[k].w;nowvalue+=i*g[k].v;bagG[k]=i;j=k;if(nowweight==remainweight){for(j++;j<n;j++){bagG[j]=0;}} digui(j+1);nowweight -= i*g[k].w;nowvalue-=i*g[k].v;bagG[k]=0;}}
}int main()
{cin>>n;for(int i=0;i<n;++i){cin>>g[i].name>>g[i].w>>g[i].v;}for(int i=0;i<n;i++)g[i].key= 1.0*g[i].v/g[i].w; for(int i=0;i<n-1;i++){for(int j=0;j<i;j++)if(g[j].key < g[j+1].key ){char tname=g[j].name;g[j].name=g[j+1].name;g[j+1].name=tname;float t=g[j].v;g[j].v=g[j+1].v;g[j+1].v=t;t=g[j].w;g[j].w=g[j+1].w;g[j+1].w=t;t=g[j].key;g[j].key =g[j+1].key ;g[j+1].key =t;}} for(int i=0;i<n;i++){cout<<g[i].name<<endl;}digui(0);cout<<bestV<<endl;for(int i=0;i<n;i++){cout<<g[i].name <<":"<< bestS[i]<<endl;}return 0;
} 

 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

LeetCode例题讲解:876.链表的中间结点

给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[3,4,5] 解释&#xff1a;链表只有一个中间结点&#xff0c;值为 3 。…

kubernetes删除命名空间下所有资源

kubernetes强制删除命名空间下所有资源 在 Kubernetes 中&#xff0c;当一个命名空间处于 Terminating 状态但不会完成删除过程时&#xff0c;通常是因为内部资源没有被正确清理。要强制删除这个命名空间及其所有资源&#xff0c;你可以采取以下步骤&#xff1a; 1. 确认命名空…

渲染农场评测:6大热门云渲染平台全面比较

在3D行业中&#xff0c;选择一个合适的云渲染平台可能会令许多专业人士感到难以抉择。为此&#xff0c;我们精心准备了6家流行云渲染平台的详尽评测&#xff0c;旨在为您的决策过程提供实用的参考和支持。 目前&#xff0c;市面上主要的3D网络渲染平台包括六大服务商&#xff0…

张驰咨询六西格玛黑带培训,上海开班,质量精英的摇篮!

一、课程背景与意义 在当今竞争激烈的市场环境中&#xff0c;企业要想立于不败之地&#xff0c;就必须不断提升自身的核心竞争力。而六西格玛作为一种先进的质量管理工具和方法&#xff0c;已经被越来越多的企业所采纳。通过六西格玛黑带培训&#xff0c;学员们可以系统地掌握…

【c++算法篇】双指针(下)

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;算法笔记仓 朋友们大家好啊&#xff0c;本篇文章我们来到算法的双指针的第二部分 目录 1.有效三角形的个数2.查找总价格为目标值的两个商品3.三数之和4.四数之和5.双指针常见场景总结 1.有效三角形…

CAPL如何实现TLS握手认证

CAPL有专门的章节介绍如何实现TLS握手认证的函数: CAPL调用哪些函数实现TLS握手认证,需要了解TLS在整个通信过程的哪个阶段。 首先TCP需要建立连接,这是TLS握手的前提。当TLS握手认证完成后,可以传输数据。 所以TLS握手开始前需要确保TCP建立连接,TCP传输数据前需要确保…

基于SSM的文化遗产的保护与旅游开发系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的文化遗产的保护与旅游开发系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;…

适合年轻人的恋爱交友脱单软件有哪些?中国十大社交软件排行榜分享

交友始祖&#xff1a;Tinder 一直很受欢迎&#xff0c;可以向上扫给 super like (每日有一次免费机会)。如果双方互相 like&#xff0c;代表配对成功&#xff0c;就可以开始聊天。另外&#xff0c;每日有 10 个 top picks 供选择&#xff0c;你可以免费选一位 主力编外&#xf…

K8s源码分析(二)-K8s调度队列介绍

本文首发在个人博客上&#xff0c;欢迎来踩&#xff01; 本次分析参考的K8s版本是 文章目录 调度队列简介调度队列源代码分析队列初始化QueuedPodInfo元素介绍ActiveQ源代码介绍UnschedulableQ源代码介绍**BackoffQ**源代码介绍队列弹出待调度的Pod队列增加新的待调度的Podpod调…

数据分析:基于sparcc的co-occurrence网络

介绍 Sparcc是基于16s或metagenomics数据等计算组成数据之间关联关系的算法。通常使用count matrix数据。 安装Sparcc软件 git clone gitgithub.com:JCSzamosi/SparCC3.git export PATH/path/SparCC3:$PATHwhich SparCC.py导入数据 注&#xff1a;使用rarefy抽平的count ma…

牛客小白月赛93

B交换数字 题目&#xff1a; 思路&#xff1a;我们可以知道&#xff0c;a*b% mod (a%mod) * (b%mod) 代码&#xff1a; void solve(){int n;cin >> n;string a, b;cin >> a >> b;for(int i 0;i < n;i )if(a[i] > b[i])swap(a[i], b[i]);int num1…

图片无损压缩工具-VIKY

一、前言 Viky v3.4是一款功能强大的图片压缩工具&#xff0c;它能够提供高效的图片无损压缩服务。通过使用独特的压缩算法&#xff0c;该软件在显著减小图片文件大小的同时&#xff0c;还保持了图像的清晰度和色彩饱和度&#xff0c;确保了图像质量的优异表现。 二、软件特点…

AS-VJ900实时视频拼接系统产品介绍:两画面视频拼接方法和操作

目录 一、实时视频拼接系统介绍 &#xff08;一&#xff09;实时视频拼接的定义 &#xff08;二&#xff09;无缝拼接 &#xff08;三&#xff09;AS-VJ900功能介绍 1、功能 2、拼接界面介绍 二、拼接前的准备 &#xff08;一&#xff09;摄像机选择 &#xff08;二&a…

区块链 | NFT 水印:Review on Watermarking Techniques(三)

&#x1f34d;原文&#xff1a;Review on Watermarking Techniques Aiming Authentication of Digital Image Artistic Works Minted as NFTs into Blockchains 一个 NFT 的水印认证协议 可以引入第三方实体来实现对交易的认证&#xff0c;即通过使用 R S A \mathsf{RSA} RSA…

力扣每日一题37:解数独

目录 题目 大致思路 方法一&#xff1a;回溯剪枝&#xff08;正常人能想出来的&#xff09; 方法二&#xff1a;位运算优化剪枝 需要使用的位运算技巧 代码 位运算怎么就优化了呢&#xff1f; 方法三&#xff1a;枚举优化。 官解代码 方法四&#xff1a;舞蹈链算法 题…

FreeRTOS任务调度器

目录 1、什么是任务调度器 2、FreeRTOS中的任务调度器 2.1 抢占式调度 2.2 时间片调度 2.3 协作式调度 3、任务调度案例分析 3.1 实验需求 3.2 CubeMX配置 3.3 代码实现 3.3.1 uart.c 重定向printf 3.3.2 打开freertos.c并添加代码 3.3.4 代码现象 1、什么是任务调度…

7 系列 FPGA 产品介绍及选型

目录 Spartan-7 FPGAsArtix-7 FPGAsKintex-7 FPGAsVirtex-7 FPGAsFPGA芯片命名规则DSP资源BRAM资源Transceivers 资源Transceivers 总带宽I/O 个数及带宽参考文档 Spartan-7 FPGAs Artix-7 FPGAs Kintex-7 FPGAs Virtex-7 FPGAs FPGA芯片命名规则 DSP资源 BRAM资源 Transceiver…

day5Qt作业

服务器端 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//准备组件&#xff0c;初始化组件状态this->setFixedSize(800,600);chatwidget new QListWidge…

【Linux】Linux——Centos7安装Tomcat

1.下载Tomcat 安装包 官网地址&#xff1a;Apache Tomcat - Apache Tomcat 9 Software Downloadshttps://tomcat.apache.org/download-90.cgi 2.将下载的安装包上传到 Xftp 上&#xff0c;我是直接放到 usr 下了 3.将安装包解压到 /usr/local/ tar -zxvf apache-tomcat-9.0.8…

Java+SpringBoot+JSP实现在线心理评测与咨询系统

前言介绍 随着互联网技术的高速发展&#xff0c;人们生活的各方面都受到互联网技术的影响。现在人们可以通过互联网技术就能实现不出家门就可以通过网络进行系统管理&#xff0c;交易等&#xff0c;而且过程简单、快捷。同样的&#xff0c;在人们的工作生活中&#xff0c;也就…