2023-01-10：智能机器人要坐专用电梯把货物送到指定地点，整栋楼只有一部电梯，并且由于容量限制智能机器人只能放下一件货物，给定 K 个货物，每个货物都有所在楼层 (from) 和目的楼层 (to)，

2023-01-10
北京
本文字数：4000 字
阅读完需：约 13 分钟

2023-01-10：智能机器人要坐专用电梯把货物送到指定地点，整栋楼只有一部电梯，并且由于容量限制智能机器人只能放下一件货物，给定 K 个货物，每个货物都有所在楼层(from)和目的楼层(to)，假设电梯速度恒定为 1，相邻两个楼层之间的距离为 1，例如电梯从 10 层去往 19 层的时间为 9，机器人装卸货物的时间极快不计入，电梯初始地点为第 1 层，机器人初始地点也是第 1 层，并且在运送完所有货物之后，机器人和电梯都要回到 1 层。返回智能机器人用电梯将每个物品都送去目标楼层的最快时间。注意：如果智能机器人选了一件物品，则必须把这个物品送完，不能中途丢下。输入描述：正数 k，表示货物数量，1 <= k <= 16，from、to 数组，长度都是 k，1 <= from[i]、to[i] <= 10000，from[i]表示 i 号货物所在的楼层，to[i]表示 i 号货物要去往的楼层，返回最快的时间。

答案 2023-01-10：

状态压缩的动态规划。代码用 rust 和 solidity 编写。

代码用 solidity 编写。代码如下：

// SPDX-License-Identifier: MITpragma solidity ^0.8.17;
contract Hello{
    function main() public pure returns (int32){    int32 k = 3;    int32[] memory from = new int32[](uint32(k));    from[0] = 1;    from[1] = 3;    from[2] = 6;    // from[3] = 5;    // from[4] = 7;    int32[] memory to = new int32[](uint32(k));    to[0] = 4;    to[1] = 6;    to[2] = 3;    // to[3] = 2;    // to[4] = 8;    int32 ans = minCost2(k,from,to);
    return ans;    }
    // 正式方法  function minCost2(int32 k, int32[] memory from, int32[] memory to) public pure returns (int32){    int32 m = leftk(k);    int32[][] memory dp = new int32[][](uint32(m));    for (int32 i = 0; i < m; i++) {      dp[uint32(i)]=new int32[](uint32(k));      for (int32 j = 0; j < k; j++) {        dp[uint32(i)][uint32(j)] = -1;      }    }    return f(0, 0, k, from, to, dp);  }
  function leftk(int32 k) public pure returns (int32){    int32 ans = 1;    while (k>0){      ans*=2;      k--;    }    return ans;  }
  // 2^16 = 65536 * 16 = 1048576  // 1048576 * 16 = 16777216  function f(int32 status, int32 i, int32 k, int32[] memory from, int32[] memory to, int32[][] memory dp) public pure returns (int32){    if (dp[uint32(status)][uint32(i)] != -1) {      return dp[uint32(status)][uint32(i)];    }    int32 ans = 2147483647;    if (status == leftk(k) - 1) {      ans = to[uint32(i)] - 1;    } else {      for (int32 j = 0; j < k; j++) {        if ((status & leftk(j)) == 0) {          int32 t = 0;          if(status == 0){            t=1;          }else{            t = to[uint32(i)];          }          int32 come = abs(from[uint32(j)] - t);          int32 deliver = abs(to[uint32(j)] - from[uint32(j)]);          int32 next = f(status | leftk(j), j, k, from, to, dp);          ans = min(ans, come + deliver + next);        }      }    }    dp[uint32(status)][uint32(i)] = ans;    return ans;  }
  function abs(int32 a)public pure returns (int32){    if(a<0){      return -a;    }else{      return a;    }  }
  function min(int32 a,int32 b)public pure returns (int32){    if(a<b){      return a;    }else{      return b;    }  }
}

复制代码

代码用 rust 编写。代码如下：

use rand::Rng;use std::iter::repeat;fn main() {    let k = 3;    let mut from = vec![1, 3, 6];    let mut to = vec![4, 6, 3];    let ans1 = min_cost1(k, &mut from, &mut to);    let ans2 = min_cost2(k, &mut from, &mut to);    println!("ans1 = {}", ans1);    println!("ans2 = {}", ans2);
    let k = 5;    let mut from = vec![1, 3, 6, 5, 7];    let mut to = vec![4, 6, 3, 2, 8];    let ans1 = min_cost1(k, &mut from, &mut to);    let ans2 = min_cost2(k, &mut from, &mut to);    println!("ans1 = {}", ans1);    println!("ans2 = {}", ans2);
    let nn: i32 = 8;    let vv: i32 = 100;    let test_time: i32 = 5000;    println!("测试开始");    for i in 0..test_time {        let k = rand::thread_rng().gen_range(0, nn) + 1;        let mut from = random_array(k, vv);        let mut to = random_array(k, vv);        let ans1 = min_cost1(k, &mut from, &mut to);        let ans2 = min_cost2(k, &mut from, &mut to);        if ans1 != ans2 {            println!("出错了!{}", i);            println!("ans1 = {}", ans1);            println!("ans2 = {}", ans2);            break;        }    }    println!("测试结束");}
// 0 1 2// from = {3, 6, 2}// to = {7, 9, 1}// from[i] : 第i件货，在哪个楼层拿货，固定// to[i] : 第i件货，去哪个楼层送货，固定// k : 一共有几件货，固定// status : 00110110// last : 在送过的货里，最后送的是第几号货物// 返回值: 送完的货，由status代表，// 而且last是送完的货里的最后一件，后续所有没送过的货都送完，// 最后回到第一层，返回最小耗时// k = 7// status = 01111111// 0000000000001// 0000010000000 -1// 0000001111111fn zuo(status: i32, last: i32, k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {    if status == (1 << k) - 1 {        // 所有货送完了，回到1层去了        return to[last as usize] - 1;    } else {        // 不是所有货都送完！        let mut ans = i32::MAX;        for cur in 0..k {            // status : 0010110            //            1            if (status & (1 << cur)) == 0 {                // 当前cur号的货物，可以去尝试                // to[last]                //    cur号的货，to[last] -> from[cur]                let come = abs(to[last as usize] - from[cur as usize]);                let delive = abs(to[cur as usize] - from[cur as usize]);                let next = zuo(status | (1 << cur), cur, k, from, to);                let cur_ans = come + delive + next;                ans = get_min(ans, cur_ans);            }        }        return ans;    }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}
fn abs(a: i32) -> i32 {    if a < 0 {        -a    } else {        a    }}
// 暴力方法// 全排序代码fn min_cost1(k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {    return process(0, k, from, to);}
fn process(i: i32, k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {    if i == k {        let mut ans = 0;        let mut cur = 1;        for j in 0..k {            ans += abs(from[j as usize] - cur);            ans += abs(to[j as usize] - from[j as usize]);            cur = to[j as usize];        }        return ans + cur - 1;    } else {        let mut ans = i32::MAX;        for j in i..k {            swap(from, to, i, j);            ans = get_min(ans, process(i + 1, k, from, to));            swap(from, to, i, j);        }        return ans;    }}
fn swap(from: &mut Vec<i32>, to: &mut Vec<i32>, i: i32, j: i32) {    let tmp = from[i as usize];    from[i as usize] = from[j as usize];    from[j as usize] = tmp;    let tmp = to[i as usize];    to[i as usize] = to[j as usize];    to[j as usize] = tmp;}
// 正式方法fn min_cost2(k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {    let m = 1 << k;    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(k as usize).collect())        .take(m as usize)        .collect();    return f(0, 0, k, from, to, &mut dp);}
// 2^16 = 65536 * 16 = 1048576// 1048576 * 16 = 16777216fn f(    status: i32,    i: i32,    k: i32,    from: &mut Vec<i32>,    to: &mut Vec<i32>,    dp: &mut Vec<Vec<i32>>,) -> i32 {    if dp[status as usize][i as usize] != -1 {        return dp[status as usize][i as usize];    }    let mut ans = i32::MAX;    if status == (1 << k) - 1 {        ans = to[i as usize] - 1;    } else {        for j in 0..k {            if (status & (1 << j)) == 0 {                let come = abs(from[j as usize] - if status == 0 { 1 } else { to[i as usize] });                let deliver = abs(to[j as usize] - from[j as usize]);                let next = f(status | (1 << j), j, k, from, to, dp);                ans = get_min(ans, come + deliver + next);            }        }    }    dp[status as usize][i as usize] = ans;    return ans;}
fn random_array(n: i32, v: i32) -> Vec<i32> {    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        ans[i as usize] = rand::thread_rng().gen_range(0, v) + 1;    }    return ans;}