从网易校招编程题谈起,轻松理解有趣的0-1背包问题

2024-06-23 15:18

本文主要是介绍从网易校招编程题谈起,轻松理解有趣的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种情况:

B(k,C)=B(k1,C)max={B(k1,Cwk)+vkB(k1,C) B ( k , C ) = { B ( k − 1 , C ) 商 品 太 重 了 , 偷 不 了 该 商 品 m a x = { B ( k − 1 , C − w k ) + v k 偷 该 商 品 B ( k − 1 , C ) 不 偷 该 商 品

通过这个公式,我们可以对着三种情况作简单描述:
1. 当商品太重时,背包剩余的容量无法容纳物品( C<wi C < w i )时候,无法偷该件物品,考虑下一个物品。
2. 当背包剩余的容量可以容纳物品时(可以选择偷或者不偷):
- 不偷该商品,则排除当前物品,考虑下一个物品;
- 偷该商品,则扣除相应的物品容量,并加上获取的价值,接着考虑下一个。

由以上方法我们可以看出是一个递归的方式,直到B方法为0,求解结束,最优解即为B(N,W)。
这就是背包方法背后的数学公式,从局部求解从而实现全局问题的求解。

接下来我们通过二位数组可视化进行(以上文给到的变量设定作为模拟数据)最优求解:

enter image description here

构建物品在不同重量时的价值数组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背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1087519

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、