写点什么

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

  • 2023-01-10
    北京
  • 本文字数:4000 字

    阅读完需:约 13 分钟

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

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;}
复制代码



发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2023-01-10:智能机器人要坐专用电梯把货物送到指定地点, 整栋楼只有一部电梯,并且由于容量限制智能机器人只能放下一件货物, 给定K个货物,每个货物都有所在楼层(from)和目的楼层(to),_算法_福大大架构师每日一题_InfoQ写作社区