河源做网站优化,临沂吧网站建设,html5下载教程,北京装修公司哪家口碑好一些文章目录1. 题目2. 解题1. 题目
描述 打车派单场景, 假定有N个订单#xff0c;待分配给N个司机。 每个订单在匹配司机前#xff0c;会对候选司机进行打分#xff0c;打分的结果保存在N*N的矩阵score#xff0c;其中score[i][j]代表订单 i 派给司机 j 的分值。 假定每个订单…
文章目录1. 题目2. 解题1. 题目
描述 打车派单场景, 假定有N个订单待分配给N个司机。 每个订单在匹配司机前会对候选司机进行打分打分的结果保存在N*N的矩阵score其中score[i][j]代表订单 i 派给司机 j 的分值。 假定每个订单只能派给一位司机司机只能分配到一个订单。 求最终的派单结果使得匹配的订单和司机的分值累加起来最大并且所有订单得到分配。 题目保证每组数据的最大分数都是唯一的
示例
样例 1
输入
[[1,2,4],[7,11,16],[37,29,22]]
输出
[1,2,0]
解释
标号为0的订单给标号为1的司机获得 score[0][1] 2 分
标号为1的订单给标号为2的司机获得 score[1][2] 16 分
标号为2的订单给标号为0的司机获得 score[2][0] 37 分
所以一共获得了 2 16 37 55 分。https://tianchi.aliyun.com/oj/403958541416425656/430542446415516442
2. 解题
class Solution {
public:/*** param score: When the j-th driver gets the i-th order, we can get score[i][j] points.* return: return an array that means the array[i]-th driver gets the i-th order.*/int ans 0;//最大总和vectorint path;//选取的最佳方案vectorint orderAllocation(vectorvectorint score) {// write your code hereint n score.size();vectorbool vis(n, false);vectorint p(n);dfs(score, vis, 0, 0, p);return path;}void dfs(vectorvectorint score, vectorbool vis, int i, int val, vectorint p){if(i score.size()){if(val ans){ans val;path p;}return;}for(int j 0; j score.size(); j){if(vis[j]) continue;//物品 j 被选了vis[j] true;p[i] j; // 选取的方案 i 选取了 j 物品dfs(score, vis, i1, valscore[i][j], p);vis[j] false;}}
};54ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
