前排 Jobstreet 攪左個 coding online test...

唔知大家有無聽過, online test 小弟1000分先拎到 5xx 分,

問題完全唔係考你programming skill..係考你problem solving...
要寫一個program仔 (java/python/c/php/c++) 跟住upload上去比佢compile..過哂佢d test case就可以拎分..

大家可以試下一齊諗下, 小弟第四條contest demo question未拎到滿分...
(大家唔好諗用recursive function做, 多數死memory或者run time 太長..真係唔知佢搵乜鬼機做unit test)

http://onlinetest.jobstreet.com/index.php/

自己去開個account就得..



第四條問題...


Daniel is a planning engineer of an Marine Logistic Corporation. His daily work is to plan & manage the process of loading containers into ships. There are N containers, each with its own weights (tons) and price value (MYR) that need to be loaded into a ship that has maximum capacity of W (tons).

Help him to identify which containers should be loaded into the ship so that the total weight does not exceed the ship capacity and the total price value is highest.
Input

On the first line you are given W and N. N lines follow with two integer on each line describing the weight (tons) & price value (MYR) of each container in that order. Notes that (1 ≦ N ≦ 1000), (100 ≦ W ≦ 1000000). Each container weight is less than '10000'.
Output

You should output a single integer which is the maximum price value of selected containers.
Sample Input

4 5
1 8  
2 4
3 1
2 5  
2 3

Sample Output

13

Explanations

As the ship capacity is 4, select container 1st & 4th will get highest value: 8 + 5 = 13

Submit唔到……

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: controllers/Submit.php

Line Number: 197

Backtrace:

File: /var/www/html/home/application/controllers/Submit.php
Line: 197
Function: mkdir

File: /var/www/html/home/application/controllers/Submit.php
Line: 108
Function: _upload

File: /var/www/html/home/index.php
Line: 286
Function: require_once

真係搞限時比賽既話仲唔比佢玩死……
BTW你講既第4條咪01背包……目前最佳做法應該都係Recursion + DP……

TOP

我用php Recursive 死左...話行得太長時間,之後偷佢d test case 黎望返,佢input成過千行.....我i7咁行法都死...真係唔知用乜方法

TOP

本帖最後由 7h1r733n 於 2015-6-19 13:27 編輯
我用php Recursive 死左...話行得太長時間,之後偷佢d test case 黎望返,佢input成過千行.....我i7咁行法 ...
mlamlam 發表於 2015-6-17 23:59

唔係吓話.. i7行千零條record會死? 講出黎都你自己唔笑先好野...

樓上已經講左用乜方法... 仲係唔明就自己睇吓
https://en.wikipedia.org/wiki/Knapsack_problem

TOP