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;
}
