切割钢条【动态规划】

2024-06-15 05:58
文章标签 动态 规划 切割 钢条

本文主要是介绍切割钢条【动态规划】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

假设公司出售一段长度为i英寸的钢条的价格为Pi(i = 1, 2, ...单位:美元),下面给出了

价格表样例:

长度i    1     2     3     4     5     6     7    8     9    10

价格Pi  1     5     8     9    10   17   17  20   24    30


切割钢条的问题是这样的:给定一段长度为n英寸的钢条和一个价格表Pi,求切割方案,使

得销售收益Rn最大。当然,如果长度为n英寸的钢条价格Pn足够大,最优解可能就是完全

不需要切割。对于上述价格表样例,我们可以观察所有最优收益值Ri及对应的最优解方案:

R1 = 1,切割方案1 = 1(无切割)
R2 = 5,切割方案2 = 2(无切割)
R3 = 8, 切割方案3 = 3(无切割)
R4 = 10, 切割方案4 = 2 + 2
R5 = 13, 切割方案5 = 2 + 3
R6 = 17, 切割方案6 = 6(无切割)
R7 = 18, 切割方案7 = 1 + 6或7 = 2 + 2 + 3
R8 = 22, 切割方案8 = 2 + 6
R9 = 25, 切割方案9 = 3 + 6
R10 = 30,切割方案10 = 10(无切割)
更一般地,对于Rn(n >= 1),我们可以用更短的钢条的最优切割收益来描述它:
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,...,Rn-1 + R1) 公式I
首先将钢条切割为长度为i和n - i两段,接着求解这两段的最优切割收益Ri和Rn - i
(每种方案的最优收益为两段的最优收益之和),由于无法预知哪种方案会获得最优收益,

我们必须考察所有可能的i,选取其中收益最大者。如果直接出售原钢条会获得最大收益,我

们当然可以选择不做任何切割。

//带备忘的自顶向下法
#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 0xffffff0;
int p[110],r[110];int MEMOIZED_CUT_ROD_AUX(int n)
{if(r[n] >= 0)//检查所求值是否是已知的return r[n];int q;if(n == 0)//这里计算局部最优解q = 0;else{q = -INF;for(int i = 1;i <= n; i++)q = max(q,p[i]+MEMOIZED_CUT_ROD_AUX(n-i));}r[n] = q;//将q存入r[n],返回q值return q;
}
int MEMOIZED_CUT_ROD(int n)
{int i;for(i = 0; i <= n; i++)//全部初始化r[i] = -INF;return MEMOIZED_CUT_ROD_AUX(n);//求解
}int main()
{int N;while(~scanf("%d",&N)){for(int i = 1; i <= N; i++)scanf("%d",&p[i]);int ans = MEMOIZED_CUT_ROD(N);printf("%d\n",ans);}return 0;
}

钢条切割问题还存在一种相似的但更为简单的地柜求解方法:

我们将钢条从左边切割下长度为i的一段,只对右边剩下长度为n-i的一段惊醒切割。(递归

求解),对左边的一段则不再切割。即问题的分解方式为:将长度为n的钢条分解为左边开

始一段,以及剩余部分继续分解的结果。这样,不做任何切割的方案就可以描述为:第一段

的长度为n,收益为Pn,剩余部分长度为0,对应的收益为R0 = 0。于是我们可以得到公式I

的简化版本:

Rn = max(Pi+Rn-i)(1<=i<=n)  公式II

在此公式中,原问题的最优解只包含一个相关子问题(右端剩余部分)的解,而不是两个。

//自底向上法
#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 0xffffff0;
int p[110],r[110];//r[n]来保存子问题int BOTTOM_UP_CUT_ROD(int n)
{r[0] = 0;//长度为0的钢条没有收益for(int j = 1; j <= n; j++)//对j=1,2,3,…,n按升序求解每个规模为j的子问题。{int q = -INF;for(int i = 1; i <= j; i++){q = max(q,p[i]+r[j-i]);//直接访问数组r[j-i]来获得规模为j-i的子问题的解}r[j] = q;}return r[n];
}
int main()
{int N;while(~scanf("%d",&N)){for(int i = 1; i <= N; i++)scanf("%d",&p[i]);int ans = BOTTOM_UP_CUT_ROD(N);printf("%d\n",ans);}return 0;
}





这篇关于切割钢条【动态规划】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1062607

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

轨迹规划-B样条

B样条究竟是干啥的?白话就是给出一堆点,用样条的方式,给这些点连接起来,并保证丝滑的。 同时B样条分为准均匀和非均匀,以下为准均匀为例。 参考链接1:https://zhuanlan.zhihu.com/p/50626506https://zhuanlan.zhihu.com/p/50626506 参考链接2: https://zhuanlan.zhihu.com/p/536470972h

PMBOK® 第六版 规划进度管理

目录 读后感—PMBOK第六版 目录 规划进度管理主要关注为整个项目期间的进度管理提供指南和方向。以下是两个案例,展示了进度管理中的复杂性和潜在的冲突: 案例一:近期,一个长期合作的客户因政策要求,急需我们为多家医院升级一个小功能。在这个过程中出现了三个主要问题: 在双方确认接口协议后,客户私自修改接口并未通知我们,直到催进度时才发现这个问题关于UI设计的部分,后台开发人员未将其传递给

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b