Facebook Interview Question
Software Engineer / DevelopersIsn'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.
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)
This is one of the best puzzles i had seen uptill date
- CUNOMAD May 18, 2009