动态规划求解超详细介绍 例题+代码

简介: 动态规划求解超详细介绍 例题+代码

软件与算法设计训练 第一大题

1.某工厂计划要采购n台设备,每台设备的采购价格为pi(i=1,2…,n),工厂装备该设备后能产生的效益为vi(i=1,2,…n)。因为新冠疫情影响,该工厂大幅缩减了预算,用于本次采购的预算总金额为C。请设计采购方案算法使得产生的效益最大。
2、问题描述:新学期有n门选修课程,且每门课程的上课时间段不相同,也不与其他课程冲突,若第i门选修课课时为Ti,学分为vi ,可以选修的总课时为MaxT。请设计一个算法,使得选修课的总课时=<MaxT,而获得总学分最大。

这两个题目怎么说,很简单对不对,一看到有价格(总课时)限制,还要你求效率(学分)尽可能的多,妥妥的老贪心了,不过我喜欢动态规划,哈哈哈哈哈哈

简单的来说这就是一个典型的背包问题,说白了就是一个小偷背了一个背包潜进了金店,包就那么大,他如果保证他背出来所有物品加起来的价值最大。
在这个题目中就是在保证金额(背包总重量)的前提下,采购设备(单个物品价值),让我们的效率(总价值)max,所以采用动态规划算法。

先假设其:

总金额:10k

编号 1号机 2号机 3号机 4号机 5号机

价格(k) 2 2 6 5 4

效率 6 3 5 4 6

所以说我们现在目标明确要从5个中买入若干机器,但是总的金额不可以超过10k,可以分解为:

方案一:买入1号机,现在从其他四个里面选若干机器,但是总金额不可以超过8k,1号机已经花掉了2k。

方案二:我们不买1号机,从其他四个中选出若干机器,总金额还是原来的10k。

这两种做法中,价值最大的就是我们需要的方案

如果我们选择了第一种方案,下面继续分解:

方案一:买入2号机,现在从其他三个里面选若干机器,但是总金额不可以超过6k,老规矩,2号机已经花掉了2k。

方案二:我们不买2号机,从其他三个中选出若干机器,总金额是原来买1号机剩下的8k。
…(以此类推,直到五个机器都选择完毕。)

一般化: f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }

(i表示的几号机,j的话是我们的金额,wi单个机器价格,pi单个机器效率)

再次解读:
我们可以看到我们上面的列出的例子,也就是说,我们需要用到max,来比较我们两种方案的最优化,上面公式中还有个( j >= Wi ),表示剩余的容量至少要大于该物品的重量,才需要讨论装不装的问题。

既然子问题已经解决,那么自然想到用递归了,递归冲冲冲!!!

代码展示:

#include <iostream>
#include <algorithm>
using namespace std;
//设置实验量
int w = 10;//预算(单位k)
int s = 5;//机器数量,如果机器数量更改,后面的数组元素也要更改
int p[5] = { 2, 2, 6, 5, 4 };//单个机器的价格(单位k)
int v[5] = { 6, 3, 5, 4, 6 };//单个机器效率
int find(int n, int w)//寻找最大值    n表示总数量   w表示总预算
{
  int outcome;//返回值
  if (n == 0 || w == 0)//提前判断
  {
    return 0;
  }
  if (w < p[5 - n])//价格超过预算直接下一步
  {
    outcome= find(n - 1, w);
    return outcome;
  }
  //当n=5时,5-n表示第一件,n=4时候,5-n表示第二件
  //下面相当于创建两个分支,将不同的结果输出
  int val1 = find(n - 1, w - p[5 - n]) + v[5 - n];
  int val2 = find(n - 1, w);
  outcome = max(val1, val2);
  return outcome;
}
int main()
{
  int ret = find(s, w);
  cout << "在" << s << "台机器,预算为" << w << "k的情况下,最大效率为:" << endl;
  cout << ret << endl;
  return 0;
}

欢迎大家和我一起参考学习呀!!!【手动狗头】

相关文章
|
1月前
|
算法 测试技术 索引
动态规划算法练习题
动态规划算法练习题
26 0
|
9月前
|
存储 算法
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
52 0
|
12天前
|
算法 C++
【动态规划】斐波那契数列模型(C++)
【动态规划】斐波那契数列模型(C++)
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
|
8月前
|
存储
浅谈递归函数(最后一个例题:浅谈汉诺塔思路与代码)
浅谈递归函数(最后一个例题:浅谈汉诺塔思路与代码)
|
9月前
递归经典例题——汉诺塔
递归经典例题——汉诺塔
85 1
|
算法
贪心算法例题
贪心算法例题
78 0
|
算法
斐波那契数列两种算法和青蛙跳台阶的两种实际问题
当我们看到这样的题时,心想就是一个简单的递归调用么。 但是,我们要看到这种算法的不足之处——效率低下。 首先简单的介绍一下 :
70 0

热门文章

最新文章