【动态规划】经典例题

2023-09-27 00:32:47

一.动态规划三要素

1.最优子结构

2.状态转移方程 （核心）（一般用打表找出规律）

3.边界值

二.背包问题

（一.题目）

1.1题目描述

现在有一个背包但容量有限，最多只能装m千克宝石!有n个宝石，每个宝石都有自己的重量m和价值c。求可以装的宝石的最大价值。

1.2输入输出描述

        输入：两个整数m和n，表示背包最大容量和宝石数量

                   接下来的n行分别表示每个宝石的重量和价值

        输出：可以装的宝石的最大价值

1.3样例

输入：

8 3
2 3
5 4
5 5

输出：

8

（二.思路）

 打表找规律

 （三.核心代码）

//外遍历宝石数量 for(int i=1;i<=n;i++){//内遍历背包容量 for(int j=1;j<=m;j++){//装不下 if(j

（四.【AC代码】）

#include
using namespace std;
int w[1001],c[1001];  //分别表示物体重量和价值
int f[1001][1001];  //表示物体编号为i，背包容量为j时，最大价值 
int main(){int m,n;cin>>m>>n;for(int i=1;i<=n;i++){cin>>w[i]>>c[i];}//外遍历宝石数量 for(int i=1;i<=n;i++){//内遍历背包容量 for(int j=1;j<=m;j++){//装不下 if(j

三.买宝石

（一.题目）

1.1题目描述

假设我们有v(1

1.2输入输出描述

输入：

一个整数v表示有v种宝石，一个整数n表示有n元

v个整数分别表示每种宝石的价格

输出：

有多少种购买方案

1.3样例

输入:

3 8
1 2 5

输出：
7

（二.思路）

根据打表，可以找到边界和状态转移方程

说明：i为多少种宝石，j表示价值

1.我们可以得到边界为：（1）f[0][j]=0,f[i][0]=1;

                                        （2）if(i>1) for(j=0;j

2. 我们得到状态转移方程为：f[i][j]=f[i-1][j]+f[i][j-p]   //i为当前宝石的价格

（三.核心代码） 

略

（四.【AC】代码）

#include
using namespace std;
int v,n,p,i,j;
int f[1001][1001]; 
int main(){cin>>v>>n;for(i=1;i<=v;i++){cin>>p;//边界 f[i][0]=1;if(i>1){for(j=0;j


本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

相关文章

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销 是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题 跑道 汽车 绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce