一道关于 NAS 磁盘选购的“算法题”

2020/07/31. Golang

背景

在经历了买二手刀片机、给旧手机装 linux 等折腾之后，小明终于不想再捡垃圾了，决定花钱买一台正儿八经的 NAS 主机，来存放他那些自视珍宝的数据。

但在选择磁盘方案时，他却碰到了问题，由于磁盘的价格并不是与其容量成正比的，且不同规格的磁盘组成的阵列的空间利用率也不尽相同。那么你是否可以写一个算法，帮助他选择出性价比最高的磁盘选购方案呢？

问题

已知磁盘盘位数 X，小明的最低容量需求 Y （单位 TB），小明的最高预算 Z（单位元），以及可供选购的磁盘规格 M，M 是一个 map，key 为磁盘的容量，value 为对应的价格。

根据群晖提供的 RAID 容量计算器可知，其推荐的磁盘阵列方案 SHR (Synology Hybrid RAID) 磁盘利用率相对较高，可以简单理解为：

可用空间 = 所有磁盘空间总量 - 最大一块磁盘的空间

由于仅一块磁盘是不安全的，所以这里不考虑只用一块磁盘的方案，按照该公式，可以认为当只有一块磁盘时，（安全的）容量为零。

在满足上述条件的情况下，求一个性价比最高的方案，即每 TB 磁盘空间耗资最少。

输入

第一行输入四个整数，依次是：

盘位数 X，取值范围 [2, 12]；
最低容量需求 Y，取值范围 [1, +∞)；
最高预算 Z，取值范围 [0, +∞)；
磁盘规格种数 N，取值范围 [1, 10]。

第二行输入 N 个从小到大的不重复的整数，表示每种规格的磁盘的容量是多少。

第三行输入 N 个的整数，表示每种规格的磁盘的价格是多少。

示例：

4 6 5000 3
1 2 4
300 400 500

表示盘位数为 4，最低容量需求为 6TB，最高预算为 5000 元，且有 3 种磁盘规格供选择：

1 TB，300 元；
2 TB，400 元；
4 TB，500 元。

输出

第一行输出一个整数 A，表示有多少种可供选择的方案；

如果 A 不为 0，则按性价比（每块钱能获得多少空间）从高到低输出 A 行，一行表示一个方案，每行依次输出：

一个整数，总容量 B；
一个整数，总价格 C；
X 个从小到大的整数，表示各磁盘的容量。

示例：

6
12 2000 4 4 4 4 
8 1500 0 4 4 4 
10 1900 2 4 4 4 
9 1800 1 4 4 4 
8 1800 2 2 4 4 
7 1700 1 2 4 4

表示有 6 个可供选择的方案，其中最佳方案的容量为 12TB，价格为 2000 元，磁盘规格依次为 4TB、4TB、4TB、4TB。

解答

由于本题的输入规模非常有限，故考虑直接暴力深搜，适当剪枝。

这里给出一份没做多少优化的代码：

package main

import (
	"fmt"
	"sort"
	"strings"
)

var (
	x, y, z, n int
	m          = map[int]int{}

	solutions [][]int
)

func main() {
	fmt.Scan(&x, &y, &z, &n)

	var sizes []int
	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)
		sizes = append(sizes, v)
	}
	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)
		m[sizes[i]] = v
	}

	// 支持容量为 0、价格也为 0 的磁盘，即空闲出磁盘架位
	sizes = append([]int{0}, sizes...)

	search(x, nil, sizes)

	// 按性价比从高到低排序
	sort.Slice(solutions, func(i, j int) bool {
		return float64(price(solutions[i]))/float64(capacity(solutions[i])) < float64(price(solutions[j]))/float64(capacity(solutions[j]))
	})

	fmt.Println(len(solutions))
	for _, v := range solutions {
		fmt.Println(capacity(v), price(v), strings.Trim(fmt.Sprint(v), "[]"))
	}
}

func search(left int, solution, sizes []int) {
	if price(solution) > z {
		return
	}
	if left == 0 {
		if capacity(solution) > y {
			t := make([]int, len(solution))
			copy(t, solution)
			solutions = append(solutions, t)
		}
		return
	}
	for i, v := range sizes {
		search(left-1, append(solution, v), sizes[i:])
	}
}

// 计算指定方案的容量
func capacity(solution []int) int {
	var ret int
	for i, v := range solution {
		if i < len(solution)-1 {
			ret += v
		}
	}
	return ret
}

// 计算指定方案的价格
func price(solution []int) int {
	var ret int
	for _, v := range solution {
		ret += m[v]
	}
	return ret
}

测试

假设准备买一个 4 盘位的 NAS 主机，存储容量不低于 10 TB，磁盘预算不超过 4000 元，根据京东希捷旗舰店关于酷狼硬盘的最新价格：

有可供选择的磁盘规格：

1TB：499 元；
2TB：539 元；
3TB：759 元；
4TB：889 元；
6TB：1259 元；
8TB：1749 元；
10TB：2359 元；
12TB：2899 元；
14TB：3599 元；
16TB：4299 元。

构建输入：

4 10 4000 10
1 2 3 4 6 8 10 12 14 16
499 539 759 889 1259 1749 2359 2899 3599 4299

运行程序，得到输出：

8
12 3556 4 4 4 4 
11 3426 3 4 4 4 
12 3777 0 6 6 6 
12 3926 4 4 4 6 
12 3946 2 4 6 6 
11 3796 3 4 4 6 
11 3816 2 3 6 6 
11 3906 1 4 6 6

其中性价比最高的方案位购买 4 块 4TB 硬盘，可获得 12TB 的容量，价钱为 3556 元。

但如果愿意多花两百块，用 3777 元购买 3 块 6TB 的硬盘，同样能获得 12TB 容量，此外还能空闲出一个盘位，方便以后扩容。

等小明发工资了，就让他买。

一道关于 NAS 磁盘选购的“算法题”

目录

背景

问题

输入

输出

解答

测试