重庆网站制作和推广公司,redis做缓存的网站并发数,吃什么补肾快,苏州网站开发公司哪里济南兴田德润简介目录
一、题目大意 二、大致思路
三、具体实现 一、题目大意 一家公司购买长钢条#xff0c;将其切割成短钢条出售#xff0c;切割本身没有成本#xff0c;长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。提示…目录
一、题目大意 二、大致思路
三、具体实现 一、题目大意 一家公司购买长钢条将其切割成短钢条出售切割本身没有成本长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。提示将钢条切割为长度为i和n - i两段接着求解这两段的最优切割收益Ri和Rn - i 二、大致思路 本题用到的知识点就是动态规划以下简称DP我在解决此题的时候思路在刚开始的时候是乱着的首先是题目的意思不明确后来发现长度不同的钢条的价格可以自行输入有点“长度为5的钢条的最大价值是建立在4的基础上”的感觉即使是在有提示的情况下我还是没有思路。 我大脑里将此题与其他DP类型的题目对比准备用一个二维数组把所有的情况存储一下但是发现二维数组的横纵坐标代表的属性似乎找不全。后来豁然开朗解决本题的核心思想就是分成两段一根钢条拿来时他的最大价值将会在两种情况产生一刀也不切就切一刀。到这里有的同学可能就不理解了。让我慢慢道来此处的切一刀其实是分出一个比例我们把这个切一刀之后左右两边的比称为“最大价值比”这一刀左侧切出来的最大价值加上右边的最大价值不就是整段钢条的最大价值了吗有了这个思路之后我写出来了如下代码。做完之后再返回头思考其实这个价格表就是一个入手点我们可以根据此表把每一个不同长度的钢条的最大收益计算出来例如我有了前10个1-10长度的钢条的最大收益那么长度为11的钢条的最大收益就可以从110、29、38……..(56)来选出。这就是只切一刀的真实含义。做了几组DP题目之后自己也有了一点感觉无非是递推式已经知道1234时的最优解求5678……等时的最优解。
三、具体实现 #includestdlib.h
#includeiostream
#includestdio.h
using namespace std;
int value[1000] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//按照题目给的数据初始化之后用来记录每个长度的最优值
int abcmp(int a, int b)//比较两个int型数的大小返回大的数
{int max 0;max a b ? a : b;return max;
}
void result(int n)//用二重循环将每一个长度的钢条的最大收益记录
{int i, j;//循环变量for (i 2; i n; i)//只有2及以上单位长度才能分割所以从2开始{int max value[i];//刚开始的最大值默认是一段钢条不切的情况for (j 1; j i / 2; j)//循环条件这样的原因是//一旦j过半切割两段的情况就重复了{max abcmp(max, value[j] value[i - j]);//比较当前最大值}value[i] max;}
}
int main()
{int n 0;//钢条的长度cout 请输入钢条的长度;cin n;result(n);//调用函数cout 收益的最大值为 value[n] endl;system(pause);return 0;
}
