[DP] Rod-cutting problem

时间:2021-09-25 00:11:08

给一个长度为 n 的杆子,切成小段卖出去,价格根据小段的长度不同而不同。下面是一个例子

[DP] Rod-cutting problem

我们要通过切成小段卖出尽可能高的总价钱。问题是:How to decompose the problem?

[DP] Rod-cutting problem

Decomposition 的第一步是:第一刀切在哪?可以切在最左边(等于整根卖出去);可以切在位置1,位置2,。。。

关键的一点是,刀切下去后,左半段就不再切了,继续切右半段。切右半段就变成了一个subproblem。

Naive Recursion:

[DP] Rod-cutting problem

Top-down implementation:

[DP] Rod-cutting problem

Bottom-up implementation: 不容易构想,变量 j 是 subproblem's size,从1递增到n,变量 i 用来把每个subproblem 拆分成更小的subproblem,而根据我们这种计算的顺序,当计算 size = j 的时候,< j 的 subproblem 已经计算完毕了。

[DP] Rod-cutting problem

[DP] Rod-cutting problem的更多相关文章

  1. 动态规划法(五)钢条切割问题(rod cutting problem)

      继续讲故事~~   我们的主人公现在已经告别了生于斯,长于斯的故乡,来到了全国最大的城市S市.这座S市,位于国家的东南部,是全国的经济中心,工商业极为发达,是这个国家的人民所向往的城市.这个到处都 ...

  2. poj3311 TSP经典状压dp&lpar;Traveling Saleman Problem&rpar;

    题目链接:http://poj.org/problem?id=3311 题意:一个人到一些地方送披萨,要求找到一条路径能够遍历每一个城市后返回出发点,并且路径距离最短.最后输出最短距离即可.注意:每一 ...

  3. 递推DP HDOJ 5328 Problem Killer

    题目传送门 /* 递推DP: 如果a, b, c是等差数列,且b, c, d是等差数列,那么a, b, c, d是等差数列,等比数列同理 判断ai-2, ai-1, ai是否是等差(比)数列,能在O( ...

  4. rod cutting

    for a rod of length i the price of it si pi,to cut the rod to earn more money package dynamic_progra ...

  5. &lbrack;Java 8&rsqb; &lpar;9&rpar; Lambda表达式对递归的优化&lpar;下&rpar; - 使用备忘录模式&lpar;Memoization Pattern&rpar; &period;

    使用备忘录模式(Memoization Pattern)提高性能 这个模式说白了,就是将需要进行大量计算的结果缓存起来,然后在下次需要的时候直接取得就好了.因此,底层只需要使用一个Map就够了. 但是 ...

  6. 【HDU 5909】 Tree Cutting (树形依赖型DP&plus;点分治)

    Tree Cutting Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2 ...

  7. 10003 Cutting Sticks&lpar;区间dp&rpar;

      Cutting Sticks  You have to cut a wood stick into pieces. The most affordable company, The Analog ...

  8. UVA 10003 Cutting Sticks&lpar;区间dp&rpar;

    Description    Cutting Sticks  You have to cut a wood stick into pieces. The most affordable company ...

  9. BZOJ1003 物流运输 最短路&plus;DP

    1003: [ZJOI2006]物流运输 Description 物流公司要把一批货物从码头A运到码头B.由于货物量比较大,需要n天才能运完.货物运输过程中一般要转停好几个码头.物流公司通常会设计一条 ...

  10. 动态规划——线性dp

    我们在解决一些线性区间上的最优化问题的时候,往往也能够利用到动态规划的思想,这种问题可以叫做线性dp.在这篇文章中,我们将讨论有关线性dp的一些问题. 在有关线性dp问题中,有着几个比较经典而基础的模 ...

随机推荐

  1. ios枚举规范

  2. 【转载】James Whittaker:经营成功的测试职业生涯

    转注:这篇文章出自 James A. Whittaker ,但未找到原始出处/译者.如果有知道原始出处的朋友,可在评论这留言. 你是如何开始做测试工作的?  1989年,我在田纳西大学读研究生的时候, ...

  3. UOJ Test Round 1

    第一题: 题目大意: 给出N个字符串,字符串的前面部分都是字母且都是一样的,后面部分是数字,按照后面的数字排序.N<=10000 解题过程: 1.第一题是真良心,一开始的做法是把后面的数字分离出 ...

  4. 二、JavaScript语言--JS基础--JavaScript进阶篇--数组

    1.什么事数组 我们知道变量用来存储数据,一个变量只能存储一个内容.假设你想存储10个人的姓名或者存储20个人的数学成绩,就需要10个或20个变量来存储,如果需要存储更多数据,那就会变的更麻烦.我们用 ...

  5. IOS Crash捕获

    IOS Crash ,就两种情况:一种是异常,另一种是中断[信号量]. #include <libkern/OSAtomic.h> #include <execinfo.h> ...

  6. C&num;逻辑运算符详解

    代码如下: namespace ConsoleApplication1 { class @class { static void Main_1(string[] args) //输出用户输入的内容 { ...

  7. mvc &commat;html&period;editor怎么修改宽度 和其他属性

    <style type="text/css"> #dob { width:6em; } </style> @using (Html.BeginForm()) ...

  8. &lbrack;自制操作系统&rsqb; 图形界面&VBE工具&MMIO显存&图形库&sol;字库

    本文记录了在JOS(或在任意OS)上实现图形界面的方法与一些图形库的实现. 本文中支持的新特性: 支持基本图形显示 支持中英文显示(中英文点阵字库) 相关:VBE VESA MMIO 点阵字库 Git ...

  9. Oracle课程档案,第一天。

    sys是Oracle最高权限者 DBSNMP:简单网络管理系统 ctrl+d回到oracle目录 在SQL中输入 exit也可以 select:列 where:行 sqlplus / as sysdb ...

  10. hadoop关联文件处理

    c001.txt ------------------------------ filetype|commid|commname|addressidcomm|1|罗湖小区1|1comm|2|罗湖小区2 ...