对于每个张量,都有两种释放方式:swap 或者 重计算。 但无论选哪一种,这个张量都只能贡献一次可释放空间,大小都是对应的张量大小。
所以对第 i 个张量而言:
在大模型训练中,为解决 NPU 显存不足的问题,通常采用张量 swap 或者张量重计算的方式进行优化;张量 swap 是把张量的数据先搬到 CPU ,需要的时候,再从 CPU 搬回 NPU ;张量重计算是在需要张量的值时,在 NPU 上重新把张量的值计算出来。
试着编写一段程序,从 n 个候选张量中选择合适的张量进行 swap 或者重计算,在代价最小的情况下,使得大模型能够运行起来(选择的张量和大于等于 m )。
第一行为 1 个整数 m(0<m<10000),表示需要的存储空间大小
第二行为 1 个整数 n(0<n<10000),表示候选张量的个数
第三行有 n 个处于区间 [1,100000] 之内的整数,表示 n 个候选张量的存储空间大小
第四行有 n 个处于区间 [1,100000] 之内的整数,表示 n 个候选张量 swap 的代价
第五行有 n 个处于区间 [1,100000] 之内的整数,表示 n 个候选张量重计算的代价
如果没有找到合适的解,输出 error ;否则,输出最小代价(行尾没有空格)。
输入
10
5
3 4 5 6 7
1 2 3 5 5
2 3 4 5 6
输出
6
说明
需要的存储空间是 10 ;
候选张量长度分别为 3,4,5,6,7;
张量长度组合 3+7,4+6,5+6,5+7,6+7,3+4+5,... 都大于等于 10 ,满足运行的基本条件;
对于 3+7 来说,3 的最小代价是 1,7 的最小代价是 5 ,3+7 的最小代价是 6;
经过其他组合的比较,达到目标的最小代价是 6 ,所以输出 6 。
输入
12
4
18 20 10 12
12 3 13 4
10 14 10 1
输出
1
说明
需要的存储空间是 12;
候选张量长度分别为 18,20,10,12;
张量长度 18,20,12 都大于等于 12 ,满足运行的基本条件;
其中 12 的代价最小为 1 ,所以输出 1 。