从网易校招编程题谈起,轻松理解有趣的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

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给