工作中遇到一个场景，可以用动态规划解决
需求场景
有一笔预算金额，要分配给若干员工，预算金额、员工数量、每个员工的工资都是已知数，如何分配可以尽可能用完这笔预算金额？
需求价值
预算金额是需要申请和审批的，如果利用率提高了，可以降低申请、审批预算的成本
示例
假设有5个员工，工资依次是10、5、3、4、11。
从5个员工中取出1-5个人，打包成一个账单，账单金额不能超过预算20。
如何分配可以尽可能用完这20元？
思路分析
典型的动态规划-01背包问题是这样的
有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
本次需求场景，其实就属于01背包，只需要转换一下概念
容量 -> 预算金额
物品 -> 员工
体积 -> 员工工资
价值 -> 员工工资
实现1（不推荐）
/**
* 有一笔预算金额，要分配给若干员工，预算金额、员工数量、每个员工的工资都是已知数，如何分配可以尽可能用完这笔预算金额？
* @param salarys 每个员工的工资，下标从1开始
* @param bugdet 预算金额
* @return 预算的最大分配金额
*/
public static int getMaxMoney1(int[] salarys, int bugdet) {
// 员工数量，salarys[0]无效
int employeeCount = salarys.length - 1;
// dp[i][j]表示预算j分配给第1至i个员工的最大分配金额
int[][] dp = new int[employeeCount + 1][bugdet + 1];
// 初始化dp数组
for (int j = 0; j <= bugdet; j++) {
dp[1][j] = salarys[1] > j ? 0 : salarys[1];
}
for (int i = 1; i <= employeeCount; i++) {
for (int j = 1; j <= bugdet; j++) {
// 如果第i个人的工资 > 预算j，那么dp[i][j] = 预算j给前i-1个人用的最优解
if (salarys[i] > j) {
dp[i][j] = dp[i - 1][j];
continue;
}
// 情况1，如果第i个员工不参与结算，dp[i][j] = 预算j分配给第1至i-1个员工的最大分配金额
int value1 = dp[i - 1][j];
// 情况2，如果第i个员工参与结算，dp[i][j] = (预算j-salarys[i])分配给第1至i-1个员工的最大分配金额 + salarys[i]
int value2 = dp[i - 1][j - salarys[i]] + salarys[i];
dp[i][j] = Math.max(value1, value2);
}
}
return dp[employeeCount][bugdet];
}
实现2（推荐）
/**
* 有一笔预算金额，要分配给若干员工，预算金额、员工数量、每个员工的工资都是已知数，如何分配可以尽可能用完这笔预算金额？
* @param salarys 每个员工的工资，下标从1开始
* @param bugdet 预算金额
* @return 预算的最大分配金额
*/
public static int getMaxMoney2(int[] salarys, int bugdet) {
// dp[j]表示预算为j时的最大分配金额
int[] dp = new int[bugdet + 1];
for (int i = 1; i < salarys.length; i++) {
for (int j = bugdet; j >= salarys[i]; j--) {
// 情况1，如果第i个员工不参与结算，那么dp[j] = 预算j分配给第1至i-1个员工的最大分配金额，即前面算出的dp[j]
int value1 = dp[j];
// 情况2，如果第i个员工参与结算，那么dp[j] = (预算j-salarys[i])分配给第1至i-1个员工的最大分配金额 + salarys[i]
int value2 = dp[j - salarys[i]] + salarys[i];
dp[j] = Math.max(value1, value2);
}
}
return dp[bugdet];
}
运行示例
public static void main(String[] args) {
int[] salarys1 = new int[]{-1, 13, 8, 10, 30, 6};
int bugdet1 = 20;
// 运行结果: result1: 19, result2: 19
log.info("result1: {}, result2: {}", getMaxMoney1(salarys1, bugdet1), getMaxMoney2(salarys1, bugdet1));
int[] salarys2 = new int[]{-1, 10, 5, 3, 4, 11};
int bugdet2 = 20;
// 运行结果: result1: 20, result2: 20
log.info("result1: {}, result2: {}", getMaxMoney1(salarys2, bugdet2), getMaxMoney2(salarys2, bugdet2));
}
小数的处理
Q: 上面的实现1和实现2，都是把金额作为数组下标，假如预算金额和工资都可以是小数，怎么办？
A: 把预算金额向下取整，再用于分配金额。把dp数组定义成double，这样就可以满足工资是小数。
思考
- 动态规划算法，有一定套路可循
第1步: 定义dp数组
第2步: 写出状态转移方程
第3步: 根据状态转移方程计算dp数组 - 同一道题，dp数组的定义可以有多种思路，定义得好，实现起来简单很多，比如本案例实现2比实现1简单得多
- 不管是实现1还是实现2，dp数组的空间复杂度是个问题，假设bugdet是100w，一个double类型变量占8字节，那么dp数组大小约8M
- 如何记录最后哪些人参与了结算？问题转换为“01背包记录路径”，网上有不少解法
网友评论