本文主要是介绍从网易校招编程题谈起,轻松理解有趣的0-1背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
从网易的一道算法题开始
最近在准备春招实习,偶然做到网易的一道编程题,一方面找了很多博客看的云里雾里,这里特别写下解题的思路和逻辑,一方面加深印象,另一方面供需要的你学习参考。好了,话不多说,开始吧。本文提供思路,并给出Java代码实现例子,供大家参考。
先睹为快
来源:网易2017春招笔试真题编程题 时间限制:1秒 空间限制:32768K
一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理,现在需要设计一个方案让CPU处理完这批任务所需的时间最少,求这个最小的时间。
输入描述: 输入包括两行: 第一行为整数n(1 ≤ n ≤ 50) ,第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304),表示每个任务的长度为length[i]kb,每个数均为1024的倍数。
输出描述: 输出一个整数,表示最少需要处理的时间
输入例子1: 5 3072 3072 7168 3072 1024
输出例子1: 9216
思路分析:
由题目分析可以知道,核1和核2同时工作的问题,我们可以分成两种情况进行考虑。
题设:总处理任务时间为SUM,核1处理时间为sum1,核2处理时间为sum2,CPU处理时间为:runtime
1. 理想化情况:在理想的情况可以将任务处理长度分成两组,这两组的消耗时长相同(即sum1=sum2
),此时CPU处理的时间为: SUM/2
2. 不理想理想:此时仍然分成两组,但sum1≠sum2,这时候CPU的处理时间runtime = max{sum1,sum2}。很显然的是,核1与核2处理总时间之和是固定的,即为全部作业总耗时。很容易转化为:找到一种分配方法,使得核1与核2处理作业耗时只差最短。综上所述:让sum1和sum2更加接近SUM/2即可达到最小的CPU处理时间的目的。
转化为0-1背包问题求解:
根据动态规划中的0-1背包问题原理,上述问题也可以进行转化:
即可转化为0-1背包问题:若完成任务总共花费的时间应该为t,不过由于是双核,要以最短时间完成任务,应该使得两核花费的时间最接近,也就是最接近t/2,最好情况下就是两核花费时间都为t/2了。设背包容量是sum/2. 每个物体的体积是数的大小,然后尽可能的装满背包。
好这里就简单论述,不做具体展开,看不懂也没关系,我们往下深入解析背包问题,再回过头来看。
0-1背包问题理解(Knapsack)
假定背包的最大容量为W,N件物品,每件物品都有自己的价值和重量,将物品放入背包中使得背包内物品的总价值最大。
从一个场景分析
可以想象这样一个场景:小偷带着一个包来偷东西,背包的重量有限(W),屋子里物品数量有限(N),每件物品都具有一定的重量(w[ ])和价值(v[ ]),对于一件物品他只能选择带走或者不带走。
变量设定
Knapsack Max weight(背包容量) : W = 10 (units)
Total items(物品总件数) : N = 4
Values of items(物品价值) : v[] = {10, 40, 30, 50}
Weight of items(物品重量) : w[] = {5, 4, 6, 3}
从示例数据大致估算一下,最大重量为10时(W=10)背包能容纳的物品最大价值为50+40=90,重量为7。
解决方案
这是一个典型的动态规划算法问题:先得到该问题的局部解然后扩展到全局问题解。
我们可以假设一个B(k,C) 方法,第k件物品,当前背包所剩下的容量C(初始则C=W)情况下,能够偷的最大价值量。
时对于每件物品关于偷与不偷可以分成以下3种情况:
通过这个公式,我们可以对着三种情况作简单描述:
1. 当商品太重时,背包剩余的容量无法容纳物品( C<wi C < w i )时候,无法偷该件物品,考虑下一个物品。
2. 当背包剩余的容量可以容纳物品时(可以选择偷或者不偷):
- 不偷该商品,则排除当前物品,考虑下一个物品;
- 偷该商品,则扣除相应的物品容量,并加上获取的价值,接着考虑下一个。
由以上方法我们可以看出是一个递归的方式,直到B方法为0,求解结束,最优解即为B(N,W)。
这就是背包方法背后的数学公式,从局部求解从而实现全局问题的求解。
接下来我们通过二位数组可视化进行(以上文给到的变量设定作为模拟数据)最优求解:
构建物品在不同重量时的价值数组B(Value数组):B[N][W] = 4 rows * 10 columns,该矩阵中的每个值的求解都代表一个更小的背包问题。(行方向代表着不同的物品,列方向表示当前不同的背包剩余容量,一般动态规划都是从B[1][1]元素开始行方向上遍历)
初始情况一:对于第0列,它的含义是背包的容量为0。此时物品的价值呢?没有。因此,第一列都填入0。
初始情况二:对于第0行,它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢?还是没有!所有都是0。
B[k][C]的含义 :以图中红色框中的40为例,代表的含义为:B(2,5)情况下的最大值为40。
回到网易的编程题
// 核心代码
int[][] B = new int[N + 1][W + 1];
for (int k = 1; k <= N; k++) {for (int C = 1; C <= W; C++) {if(w[k] > C){ // 如果当前物品重量大于当前背包剩余容量Capacity则偷不了,考虑下一个商品
B[k][C] = B[k-1][C];
}
else{ // 如果背包容量大于物品,则两种情况下选出最大值
int value1 = B[k-1][C]; // 不偷
int value2 = B[k-1][C-w[k]] + w[k]; // 偷
B[k][C] = Math.max(value1,value2);
}
}
}
Java代码实现
import java.lang.*;
import java.util.*;public class Main {public static void main(String[] args) {int N = 0;Scanner scanner = new Scanner(System.in);N = Integer.valueOf(scanner.nextLine());int[] w = new int[N+1]; // 存放所有任务int sum = 0;for (int i = 1; i < N+1; i++) {w[i] = scanner.nextInt()/1024;sum += w[i];}int W = sum /2;int[][] B = new int[N + 1][W + 1];for (int k = 1; k <= N; k++) {for (int C = 1; C <= W; C++) {if(w[k] > C){ // 如果当前物品重量大于当前背包剩余容量Capacity则偷不了,考虑下一个商品B[k][C] = B[k-1][C];}else{ // 如果背包容量大于物品,则两种情况下选出最大值int value1 = B[k-1][C]; // 不偷int value2 = B[k-1][C-w[k]] + w[k]; // 偷B[k][C] = Math.max(value1,value2);}}}System.out.print(Math.max(B[N][sum / 2], sum - B[N][sum / 2]) * 1024);}
}
参考资料:
- 如果觉得本文晦涩难懂,推荐这个视频(32mins):【经典算法】01背包问题_土豆视频
- 从一道算法题谈起,有趣的0-1背包问题
- Knapsack算法可视化数组模拟
- 如何理解背包问题电脑软件百度经验
联系作者
- CSDN博客:http://blog.csdn.net/u012104219
- 知乎专栏:https://zhuanlan.zhihu.com/frankfeekr
- Github:https://github.com/frank-lam
- Email:frank_lin@whu.edu.cn
如果你觉得不错的话,不妨打赏一下,这样我就有更大的动力去完善它,优化它。
这篇关于从网易校招编程题谈起,轻松理解有趣的0-1背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!