CareerCup

1) Use knapsack problem to find the minimum value(instead of maximum) for Weight W. In the original algo instead of taking maximum value take minimum value for each Array[i] , 0<i<=W.

2) Now for each value of n, find the minimum index i in Array such that i+w[n]> W and note the value as Array[i]+v[n]. Update this value if the old value is greater than the new value

The question in itself seems incomplete.

The question in itself seems incomplete.

what about doing normal knapsack , but storing the coins that are actually going in . After that run through the coins until you find one that is not in knapsack. (Consider first sorting the coins)

we can assume all weights wi are smaller than w, otherwise just return min(vi) among wi's that exceed w.
Find the max among wi, say w_max , then apply knapsack on w+w_max -1 to find the minimum value. Scan through the list from w+1 to w+w_max-1 to find the min value here(besides 0s) . The min value here should be the answer.

TreeSet<Integer> possibleValues = …;

void fillAllPossiblevalues(List<Integer> values, List<Integer> weights, Integer weightLimit, int valueStored) {
	possibleValues.add(valueStored);

	for (int i =0 ; i<weights.size(); i++) {
		if (weightLimit < weights.get(i)) continue;
		fillAllPossibleValues(values,weights, weightLimit -weights.get(i), valueStored + values.get(i));
		
}
}

Now,
int minsoFar = 0;
for (Integer value : possibleValues) { //this will be in increasing order
	if (value!=++minsoFar) {
	return misoFar;
}
}

here is my solution. I think the complexity is bad.

If someone has better implementation.
Please give out. I will very appreciate.

int KnapSack(int capacity, int v[], int w[], int index, int num) {
	if(capacity<0 || index>=num)
		return 10000;

	if(capacity == 0)
		return 0;

	int a = v[index] + KnapSack(capacity-w[index], v, w, index, num);
	int b = KnapSack(capacity, v, w, index+1, num);
	return min(a, b); 
}

int SmallestImpossible(int v[], int w[], int capacity, int num) {
	int smallest = 10000, c = 0;

	for(int i=0; i<num; i++) {
		int tmp = KnapSack(capacity+w[i], v, w, 0, num);
		if(tmp < smallest) {
			smallest = tmp;
			c = capacity+w[i];
		}
		//cout << capacity+w[i] << " " << tmp << endl;
	}	
	return smallest;
}

so for the first part this is what I feel: if denominations start from 1 then there is no value that is not possible (cause the coins are unlimited). If the smallest denomination is >1 then 1 is the smallest value that is not possible.