CareerCup

This is one of the best puzzles i had seen uptill date

Isn't this the unbounded knapsack problem, which is NP Hard?

There are greedy (approximation) algorithms: eg: just use the sku with least cost per unit weight, but that won't give optimal (hence an approximation algorithm).

A lot of literature on these problems exists, just look it up on the web.

Of course, the assumption is that you can pick only an integer numnber of SKUs to be chucked and the input gives the weight and cost of 1 such unit.

Someone has added this to the "Request for Help" Section. Why? LOLer post's answer this. How much spoon feeding do you need?

Yes. Bounded knapsack suits this. Do some looking up on the web.

Dynamic programming.

Dynamic programming. I've passed the Facebook robot.

I also think it is NP-Complete. Integer linear programming?

any hints on approaches to take? Sort the SKUs by cost first? by weight?

They asked me to discuss about how to solve this problem ..

All these lengthy description points to knapsack problem I guess :)

Dynamic Programming

Awesome!! This is valid question in linux world :-)

called out of memory problem .. google for it (oom killer)

Can we drop partial items or we have to drop the complete item?
Because if we are allowed to drop partial item this problem becomes
a variant of fractional knapsack, which can be solved by greedy algorithm.

I had some very similar question at my Amazon on-site interview too.

static int minDump(Cargo[] set, int weight, int value, int currentMin)
    {
	if (value > currentMin)
	{
	    return currentMin;
	}
	
	if (weight < 0)
	{
	    return value;
	}

	int min = currentMin;

	for (Cargo cargo : set)
	{
	    min = java.lang.Math.min(min, minDump(set, weight-cargo.weight, value + cargo.value, min));
	}

	return min;
    }

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <climits>

using namespace std;

int main(){
int W;
cin>>W;
int n;
cin>>n;
int c[n+1], w[n+1];
int s=0;
for(int i=1;i<=n;++i){
cin>>w[i]>>c[i];
s+=w[i];
}
long long int dp[s+1][n+1];
for(int i=0;i<=n;++i){
dp[0][i]=0;
}
for(int i=1;i<=s;++i){
dp[i][0]=INT_MAX;
}
int f=0;
long long int ans=INT_MAX;
for(int i=1;i<=s;++i){
for(int j=1;j<=n;++j){
dp[i][j]=min(dp[i-w[j]][j]+c[j], dp[i][j-1]);
}
if(i>=W && dp[i][n]!=INT_MAX){
f=1;
ans=min(ans, dp[i][n]);
//break;
}
}
cout<<ans<<endl;
return 0;
}

Its a modification of Knapsack problem, where,

1250 = total capcity of knasack
Item 1 :
w = 1300 , v = 10500
Item 2 :
w = somevalue , v = some value

now have to select subset of items whose total weight is less than the capacity and have min value. ( in Knapsack we select items having max value)