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);

    }

Read full article from Facebook: User Bin Crash | Lucky's Notes