## Monday, May 16, 2016

### Facebook: User Bin Crash | Lucky's Notes

Facebook: User Bin Crash | Lucky's Notes
You're on a plane, and somehow you have to dump some cargo or else it will crash. You know how much you need to dump (in pounds), and also an inventory of the items you can dump.
Each item in the inventory has a certain weight, and a certain value. By dumping a combination of the items, you have to dump at minimum the given weight, while minimizing the loss.
You can only dump integral amounts of an item (you can't dump three quarters of a package), but you're allowed to dump any amount of the item.
The program you write takes the parameters and outputs the minimum loss (value of items that are dumped).
However there’s something we can do about it. We can divide all weights by a common factor, and the result would be the same. In the example we can simply divide 13000000, 5000000, and 3000000 all by a million.
Needless to say, this would fail badly if W had been, for instance, 13000001.

`    ``public` `static` `void` `main(String[] args) ``throws` `Exception{`

`        ``BufferedReader in = ``new` `BufferedReader(`
`            ``new` `FileReader(args[``0``]));`

`        ``// Minimum weight to prevent crash`
`        ``int` `crashw = Integer.parseInt(in.readLine());`

`        ``// List containing weights of items`
`        ``List<Integer> itemW = ``new` `ArrayList<Integer>();`

`        ``// List containing values of items`
`        ``List<Integer> itemV = ``new` `ArrayList<Integer>();`

`        ``String parse;`
`        ``while``( (parse = in.readLine()) != ``null``){`
`            ``Scanner scn = ``new` `Scanner(parse);`
`            ``scn.next();`

`            ``itemW.add(scn.nextInt());`
`            ``itemV.add(scn.nextInt());`
`        ``}`

`        ``// Take the GCD's before starting the DP`
`        ``int` `gcd = crashw;`
`        ``for``(``int` `i : itemW) gcd = gcd(gcd, i);`

`        ``// Divide all weights by gcd`
`        ``crashw /= gcd;`
`        ``for``(``int` `i=``0``; i<itemW.size(); i++)`
`            ``itemW.set(i, itemW.get(i)/gcd);`

`        ``// Calculate optimal fit using dynamic programming`
`        ``int``[][] dp = ``new` `int``[itemW.size()][crashw+``1``];`

`        ``// First row of DP array done separately`
`        ``dp[``0``][``0``] = ``0``;`
`        ``for``(``int` `j=``1``; j<=crashw; j++){`

`            ``int` `aW = itemW.get(``0``);`
`            ``int` `aV = itemV.get(``0``);`

`            ``if``(aW > j) dp[``0``][j] = aV;`
`            ``else` `dp[``0``][j] = aV + dp[``0``][j-aW];`
`        ``}`

`        ``// Filling up the rest of the DP array`
`        ``for``(``int` `i=``1``; i<dp.length; i++){`

`            ``dp[i][``0``] = ``0``;`
`            ``for``(``int` `j=``1``; j<=crashw; j++){`

`                ``int` `iW = itemW.get(i);`
`                ``int` `iV = itemV.get(i);`

`                ``// Cell directly up from current`
`                ``int` `imUp = dp[i-``1``][j];`

`                ``// Cell left of it by iW`
`                ``int` `imLeft = ``0``;`
`                ``if``(iW > j) imLeft = iV;`
`                ``else` `imLeft = iV + dp[i][j-iW];`

`                ``// Smallest of the two`
`                ``dp[i][j] = imUp<imLeft? imUp: imLeft;`
`            ``}`
`        ``}`

`        ``System.out.println(dp[itemW.size()-``1``][crashw]);`
`    ``}`

`    ``// GCD using the Euclid algorithm`
`    ``static` `int` `gcd(``int` `a, ``int` `b){`
`        ``if``(b == ``0``) ``return` `a;`
`        ``return` `gcd(b, a%b);`
`    ``}`