2023-01-10：智能机器人要坐专用电梯把货物送到指定地点， 整栋楼只有一部电梯

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: MIT
pragma 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
// 0000001111111
fn 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 = 16777216
fn 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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接