文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 回溯超時
    • 2.2 狀態壓縮DP

1. 題目

在由 2D 網格表示的校園里有 n 位工人（worker）和 m 輛自行車（bike），n <= m。所有工人和自行車的位置都用網格上的 2D 坐標表示。

我們為每一位工人分配一輛專屬自行車，使每個工人與其分配到的自行車之間的曼哈頓距離最小化。

p1 和 p2 之間的曼哈頓距離為 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

返回每個工人與分配到的自行車之間的曼哈頓距離的最小可能總和。

示例 1：

輸入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] 輸出：6 解釋： 自行車 0 分配給工人 0，自行車 1 分配給工人 1 。 分配得到的曼哈頓距離都是 3, 所以輸出為 6 。

示例 2：

輸入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] 輸出：4 解釋： 先將自行車 0 分配給工人 0， 再將自行車 1 分配給工人 1（或工人 2）， 自行車 2 給工人 2（或工人 1）。 如此分配使得曼哈頓距離的總和為 4。提示： 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000 所有工人和自行車的位置都不相同。 1 <= workers.length <= bikes.length <= 10

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/campus-bikes-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 回溯超時

22 / 44 個通過測試用例

class Solution {int mindis = INT_MAX; public:int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {int nw = workers.size(), nb = bikes.size(), i, j;vector<vector<int>> dis(nw, vector<int>(nb));vector<bool> vis(nb, false);for(i = 0; i < nw; ++i)for(j = 0; j < nb; ++j)dis[i][j] = abs(workers[i][0]-bikes[j][0])+ abs(workers[i][1]-bikes[j][1]);dfs(workers, bikes, vis, dis, 0, 0);return mindis;}void dfs(vector<vector<int>>& workers, vector<vector<int>>& bikes,vector<bool> &vis, vector<vector<int>> &dis, int idx, int distance){if(idx == workers.size()){mindis = min(mindis, distance);return;}for(int i = 0; i < bikes.size(); ++i){if(vis[i]) continue;vis[i] = true;if(distance < mindis)dfs(workers, bikes, vis, dis, idx+1, distance+dis[idx][i]);vis[i] = false;}} };

2.2 狀態壓縮DP

• 參考大力王的題解

類似題目：LeetCode 5387. 每個人戴不同帽子的方案數 hard

class Solution { public:int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {int m = workers.size(), n = bikes.size(), i, j;vector<vector<int>> dis(m, vector<int>(n));for(i = 0; i < m; ++i)for(j = 0; j < n; ++j)dis[i][j] = abs(workers[i][0]-bikes[j][0])+ abs(workers[i][1]-bikes[j][1]);int M = 1 << m, N = 1 << n;//每個人或者自行車都看成一個二進制位，0還沒選，1選了vector<vector<int>> dp(M, vector<int>(N, 1000000));for(i = 0; i < m; ++i)for(j = 0; j < n; ++j)dp[1<<i][1<<j] = dis[i][j];for(i = 0; i < M; ++i)for(j = 0; j < N; ++j){int i_ = i, j_ = j;m = i&(-i);//二進制數最后一個1代表的數值lowbitn = j&(-j);while(m > 0)//遍歷之前的人的狀態{dp[i][j] = min(dp[i][j], dp[i-m][j-n]+dp[m][n]);//i-m表示少了？個1，少了？個人//j-n表示少了？輛車i_ -= m;//減掉一個人m = i_&(-i_);}m = i&(-i);//二進制數最后一個1代表的數值lowbitn = j&(-j);while(n > 0)//遍歷之前的車子狀態{dp[i][j] = min(dp[i][j], dp[i-m][j-n]+dp[m][n]);//i-m表示少了？個1，少了？個人//j-n表示少了？輛車j_ -= n;//減掉一輛車n = j_&(-j_);}}return *min_element(dp[M-1].begin(), dp[M-1].end());} };

1376 ms 39 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1066. 校园自行车分配 II（状态压缩DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。