今天晚上的华为笔试第三题有做出来的吗?求思路

耗了一个半小时也没做出来,凉凉#笔试题目#
全部评论
来个java版的 全ac的背包   public static void main(String[] args) { Scanner sc = new Scanner(System.in); int money = sc.nextInt(); List<Integer> list = new ArrayList<>(); while (sc.hasNext()) { list.add(sc.nextInt()); } int[] cost = new int[list.size() / 2]; int[] earn = new int[list.size() / 2]; int[] chosen = new int[list.size() / 2]; for (int i = 0; i < list.size(); ++i) { if (i < list.size() / 2) { cost[i] = list.get(i); chosen[i] = 0; } else { earn[i - list.size() / 2] = list.get(i); } } // d[i][j]表示前i个物品放入容量为j的背包的最大价值 // d[i][j] = max(d[i-1][j], d[i-1][j-weights[i]] + values[i]) int[][] d = new int[cost.length][money + 1]; for (int i = 0; i < d.length; ++i) { for (int j = 1; j < money + 1; ++j) { if (i == 0) { if (cost[i] <= j) { d[i][j] = cost[i]; } } else { if (j >= cost[i]) { d[i][j] = Math.max(d[i - 1][j], d[i - 1][j - cost[i]] + earn[i]); } else { d[i][j] = d[i - 1][j]; } } } } int ii = cost.length - 1, jj = money; while (ii >= 0) { if (ii > 0) { if (jj-cost[ii] >= 0 && d[ii][jj] == d[ii - 1][jj - cost[ii]] + earn[ii]) { chosen[ii] = 1; jj -= cost[ii]; } } else { if (cost[ii] <= jj) { chosen[ii] = 1; } } ii--; } boolean first = true; for (int i = 0; i < chosen.length; ++i) { if (chosen[i] == 1) { if (first) { System.out.print(i + 1); first = false; } else { System.out.print(" " + (i + 1)); } } } }
点赞 回复 分享
发布于 2018-04-03 22:50
来个 Python AC的 coding=utf-8 def bag(n, c, w, v): res = [[-1 for j in range(c + 1)] for i in range(n + 1)] for j in range(c + 1): res[0][j] = 0 for i in range(1, n + 1): for j in range(1, c + 1): res[i][j] = res[i - 1][j] if j >= w[i - 1] and res[i][j] < res[i - 1][j - w[i - 1]] + v[i - 1]: res[i][j] = res[i - 1][j - w[i - 1]] + v[i - 1] return res def show(n, c, w, res): x = [0 for i in range(n)] j = c for i in range(n,0,-1): if res[i][j] > res[i - 1][j]: x[i - 1] = 1 j -= w[i - 1] for i in range(n): if x[i]==1: print(i+1), if name == 'main': c = int(raw_input()) w = raw_input() w = w.split() for i in range(len(w)): w[i] = int(w[i]) v = raw_input() v = v.split() for i in range(len(v)): v[i] = int(v[i]) n = len(v) res = bag(n, c, w, v) show(n, c, w, res)
点赞 回复 分享
发布于 2018-04-03 22:56
深搜,第一遍深搜找最大价值,第二遍深搜找路径(本来想用背包做的,发现不会记录路径就换方法了)
点赞 回复 分享
发布于 2018-04-03 21:20
直接递归就AC了
点赞 回复 分享
发布于 2018-04-03 21:22
背包60,不知道为什么
点赞 回复 分享
发布于 2018-04-03 21:22
背包60+1 dp数据我一步一步演算的,还是过不了神奇的测试用例
点赞 回复 分享
发布于 2018-04-03 21:27
solve(); function solve () {     let         total = parseInt(readline()), // 总流量         consume = readline().split(/\s+/).map(s => Number(s)), // 每个app消耗的流量         coin = readline().split(/\s+/).map(s => Number(s)); // 每个app的金币数     let buffer = [];     for (let i = 0; i < consume.length + 1; i++) {         buffer[i] = [0];     }     for (let w = 0; w < total + 1; w++) {         buffer[0][w] = 0;     }     for (let w = 1; w < total + 1; w++) {         for (let i = 1; i < consume.length + 1; i++) {             if (consume[i - 1] > w) {                 buffer[i][w] = buffer[i - 1][w];             } else {                 buffer[i][w] = Math.max(buffer[i - 1][w], coin[i - 1] + buffer[i - 1][w - consume[i-1]]);             }         }     }     let result = [];     let w = total;     for (let i = consume.length; i > 0; i--) {         if (buffer[i][w] === buffer[i-1][w]) {             continue;         } else {             result.push(i);             w -= consume[i - 1];         }     }     print(result.reverse().join(' ')); } 背包的解法
点赞 回复 分享
发布于 2018-04-03 22:20
01背包记录路径
点赞 回复 分享
发布于 2018-04-03 23:01
典型背包问题,5分钟AC
点赞 回复 分享
发布于 2018-04-03 23:39
背包问题输出背包序列。
点赞 回复 分享
发布于 2018-04-04 08:25

相关推荐

01-07 15:50
四川大学 Java
明远湖摸鱼:同年级的同学,,简历可以大一点,这个有点太密集了,实习技术可以量化的尽量量化
点赞 评论 收藏
分享
会飞的猿:我看你想进大厂,我给你总结一下学习路线吧,java语言方面常规八股要熟,那些java的集合,重点背hashmap八股吧,jvm类加载机制,运行时分区,垃圾回收算法,垃圾回收器CMS、G1这些,各种乐观锁悲观锁,线程安全,threadlocal这些。在进阶一些的比如jvm参数,内存溢出泄漏排查,jvm调优。我这里说的只是冰山一角,详细八股可以去网上找,这不用去买,都免费资源。mysql、redis可以去看小林coding,我看你简历上写了,你一定要熟,什么底层b+树、索引结构、innodb、mvcc、undo log、redo log、行级锁表级锁,这些东西高频出现,如果面试官问我这些我都能笑出来。消息队列rabbitmq也好kafka也好,学一种就行,什么分区啊副本啊确认机制啊怎么保证不重复消费、怎么保证消息不丢失这些基本的一定要会,进阶一点的比如LEO、高水位线、kafka和rocketmq底层零拷贝的区别等等。计算机网络和操作系统既然你是科班应该理解起来问题不大,去看小林coding这两块吧,深度够了。spring boot的八股好好看看吧,一般字节腾讯不这么问,其他的java大厂挺爱问的,什么循环依赖啥的去网上看看。数据结构的话科班应该问题不大,多去力扣集中突击刷题吧。项目的话其实说白了还是结合八股来,想一想你写的这些技术会给你挖什么坑。除此之外,还有场景题、rpc、设计模式、linux命令、ddd等。不会的就别往简历上写了,虽然技术栈很多的话好看些,但背起来确实累。总结一下,多去实习吧,多跳槽,直到跳到一个不错的中厂做跳板,这是一条可行的进大厂的路线。另外,只想找个小厂的工作的话,没必要全都照这些准备,太累了,重点放在框架的使用和一些基础八股吧。大致路线就这样,没啥太多难度,就是量大,你能达到什么高度取决于你对自己多狠,祝好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务