User bin crash puzzle solution

Interesting puzzle on facebook job puzzle site. This is quick and fun puzzle to solve. Can be solve in many ways, but I choose to solve this using Knapsack approach.

You are on a cargo plane full of commercial goods when the pilot announces that the plane is short on fuel. Unless cargo is ejected from the plane, you will run out of fuel and crash. The pilot provides you with the number of pounds of weight that must be ejected from the plane. Fortunately, the manifest of the plane is both completely accurate, digitized, and you are a programmer of some repute. Unfortunately, your boss is going to be extremely unhappy, and wants you to exactly minimize the losses to the absolute minimum possible without crashing the plane. The manifest does not contain the exact quantities of every type of good, because you have so many on board. You may assume that you will not run out of any good in the course of saving the plane. You also realize this kind of program could be handy to others who find themselves in similar situations. Read More about puzzle description here.

Here is the C++ solution for the same.

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <sstream>

inline int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

int main(int argc, char *argv[]) {
    // Read the file and populate internal data structures.
    std::ifstream input(argv[1]);
    if ( input.peek() == EOF ) {
        return false;
    }
    int total_weight = 0;
    std::string file_line; 
    // Read the minimum number of pounds of weight that must 
    // be ejected from the plane to prevent a crash
    getline(input,file_line);
    std::istringstream iss;
    iss.clear();
    iss.str(file_line);
    iss >> total_weight;

    // Read all the lines in the file.
    std::vector<std::string> lines;
    getline(input,file_line);
    while( input.good() ) {
        if ( !file_line.empty())
            lines.push_back(file_line);           
        getline(input,file_line);
    }
    int num_of_items = lines.size();
    int *weights  = new int [num_of_items];
    int *costs    = new int [num_of_items];
    for(int i = 0; i < num_of_items; ++i) {
        iss.clear();
        iss.str(lines[i]);
        std::string sku = "";
        iss >> sku >> weights[i] >> costs[i] ;
    }
    input.close();
    // calculate optimize gcd.
    int overall_gcd = gcd(weights[0], total_weight);
    for(register int i = 1; i < num_of_items; ++i) {
        overall_gcd = gcd(overall_gcd, weights[i]) ;
    }
    for(register int i = 0; i < num_of_items; ++i) {
        weights[i] /= overall_gcd ;
    }   
    total_weight /= overall_gcd;

    // Solve using DP.
    int *table = new int [total_weight];
    for(register int cur_weight = 0; cur_weight < total_weight; ++cur_weight) {
        int best = -1;
        for(register int j = 0; j < num_of_items; ++j) {
            int cur_cost = costs[j];
            int item_weight = weights[j];
            if ( item_weight <= cur_weight) {
                cur_cost += table[cur_weight - item_weight];
            }
            if ( best == -1  || cur_cost < best ){
                best = cur_cost ;
            }
        }
        table[cur_weight] = best;
    }
    std::cout << table[total_weight-1] << std::endl;

    delete [] table;
    delete [] weights;
    delete [] costs;

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s