软件与算法设计训练 第一大题
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; }
欢迎大家和我一起参考学习呀！！！【手动狗头】
