CareerCup

It's look like variation of "coin change" problem where we've unlimited supply for each denomination. Solvable using DP.

@above:
its good that lol is not giving the solution. I suggest everyone to try, try n try, and not only here, in the interview also.
remembering the sequence of decisions and printing them is always tricky in DP, but u have to do it if u want to learn DP and there is no limit of DP.
I suggest that to learn DP first create a recursive solution, then use memoization (by Hash or what ever u want) and try to achieve same solution, then use as many space as u want and try to achieve again same solution and at last try to think if u can reduce the space in your previous solution, if u arrived.
you can follow these which i feel is very very good:
www(.)youtube.com/watch?v=6h6Fi6AQiRM&list=PL7DC83C6B3312DF1E
and other useful stuffs:
www(.)nptel.iitm.ac.in/

Follow completely with patience.
:)

Full code using DP is below, it also prints out the steps :)

public static int[][] minSteps(int[] a, int target){
		int[] min = new int[target+1];
		int[][] soln = new int[target+1][3];
		soln[0] = new int[]{0,0,0};
		
		for(int i =1;i<=target;i++){
			soln[i][0] = i;
			soln[i][1] = i;
			soln[i][2] = 0;
		}
		min[0] = 0;
		min[1] = 1;
		for(int i =2;i<=target;i++){
			min[i] = min[i-1]+1;
			soln[i][0] = 1;
			soln[i][1] = 1;
			soln[i][2] = i-1;
			
			for(int p=0;p<a.length;p++){
				if(a[p]==1 || i<a[p])
					continue;
				int res = i/a[p] + min[i%a[p]];
				if(res<min[i]){
					soln[i][0] = i/a[p];
					soln[i][1] = a[p];
					soln[i][2] = i%a[p];
					min[i] = res;
				}
			}
		}
		return soln;
		
	}

	private static void printSolution(int[][] solution,int target) {
		int steps = solution[target][0];
		String details = "" + solution[target][0] + " X " + solution[target][1];
		int j = solution[target][2];
		while(j!=0){
			steps += solution[j][0];
			details += " -> " + solution[j][0] + " X " + solution[j][1];
			j = solution[j][2];
		}
		System.out.println("The number of min steps are " + steps);
		System.out.println("Detailed steps are " + details);
	}

I have seen u many times talking about some pretty obvious things, can u show some guts to post your solution.I guess Anonymous,above, also knows the same what u said but he is not able to get the trick.

My recursive solution

int emptyjarrec(int a[], int size, int n, int b[])
{
    if(n==0)
        return 0;
    if(n<0)
        return INT_MAX;
    if(b[n]!=-1)
        return b[n];

    int min = INT_MAX;
    for(int i=0; i<size; i++)
        if(emptyjarrec(a, size, n-a[i], b) < min)
            min = emptyjarrec(a, size, n-a[i], b);

    b[n] = min==INT_MAX?INT_MAX:min+1;
    return b[n];
}

void emptyjar(int a[], int size, int n)
{
    static int* b = new int[n];
    for(int i=0; i<=n ;i++)
        b[i] = -1;

    emptyjarrec(a, size, n, b);

    if(b[n] == INT_MAX)
    {
        printf("NOT POSSIBLE");
        return;
    }

    int v = n;
    while(v>0)
    {
        int min = 0;
        for(int i =0; i<size; i++)
            if(v-a[i]>=0 && b[v-a[i]] < b[v-a[min]])
                min = i;
        v=v-a[min];
        printf("%d ", a[min]);
    }
}

Why cant solution be greedy? I could not think of any exaple which will prove greedy solution wrong.. even coin denomination pbm's optimal approach is greedy solution

My full code including testing, etc.

#include <hash_map>
#include <list>
#include <iostream>
#include <limits>
#include <vector>
#include <string>

using namespace std;

struct Step
{
	int bucket;
	int stepCount;
};

void findMin(int target, vector<int> &buckets)
{
	hash_map<int, Step> stepCounts;

	Step s;
	s.bucket = 1;
	s.stepCount = 1;
	stepCounts[1] = s;

	s.bucket = 0;
	s.stepCount = 0;
	stepCounts[0] = s;

	for(int t = 2; t <= target; ++t)
	{
		// the min number of steps to read the target t
		int minStepCount = numeric_limits<int>::max();

		for(int j = 0; j < buckets.size(); ++j)
		{
			if (t < buckets[j])
				break;

			int newTarget = t - buckets[j];
			if (stepCounts[newTarget].stepCount + 1 < minStepCount)
			{
				Step s;
				s.stepCount = stepCounts[newTarget].stepCount + 1;
				s.bucket = buckets[j];
				minStepCount = s.stepCount;
				stepCounts[t] = s;
			}
		}
	}

	cout << stepCounts[target].stepCount << " steps needed." << endl;
	vector<int> solnBuckets;
	while(target)
	{
		int b = stepCounts[target].bucket;
		solnBuckets.push_back(b);
		target -= b;
	}

	for(int i = 0; i < solnBuckets.size(); ++i)
		cout << solnBuckets[i] << "  ";
	cout << endl;
}

void testFindMin()
{
	vector<int> buckets;

	cout << "Enter the size of buckets, 'quit' when done." << endl;
	string inStr;
	while(cin >> inStr && inStr != "quit")
	{
		buckets.push_back(atoi(inStr.c_str()));
	}

	while(true)
	{
		cout << "Enter next target:";

		int t;
		cin >> t;
		findMin(t, buckets);
	}
}

int main()
{
	testFindMin();
}

Why such a complex solution?

#include <stdio.h>

int fill(int *conts, int numconts, int size) {
  int amount = 0;
  int cnt = 0;
  int i;

  for(i=numconts-1; i > -1 && amount < size; i--) {
    while(amount + conts[i] < size) {
      amount += conts[i];
      printf("%d ", conts[i]);
      cnt++;
    }
  }
  printf("\n%d\n", cnt);
  return 1;
}

main() {
  int conts[5] = {1, 3, 5, 6, 25};
  int numconts = 5;
  int size = 80;

  return fill(conts, numconts, size);
}

Greedy doesnt work for finding optimal soln..

Counter ex:
Tank Size: 83 litre
Containers: 1,13,20,25 litre
Solution:
4 (25,25,20,13)
Greedy soln:
11 (25,25,25,1,1,1,1,1,1,1,1)

Why to think about Dp and Greedy . This simple code works fine. I assumed the container measurements are in sorted order. I have to add sorting code if it is not the case.

public class TankFill
{
public static void main(String [] args)
{
int[] a={25,10,5,1};
int vol=71;
int i=0;
int []b=new int[100];
int n=0;
while(i<a.length)
{
int currVol=0;
int count=0;
while(a[i]*count<=vol)
{
count++;
}

currVol=a[i]*(count-1);
count--;

while(count>0)
{
b[n]=a[i];
count--;
n++;
}

vol=vol-currVol;

i++;
}
for(int h=0;h<n;h++)
{

System.out.println(b[h]);
}

}

}

Solved using DP. Algorithm of main method "fill(int tankSize)":
1. Checks exits conditions:
2. is tank size == 0? then a solution was found previous in the stack
3. is tank size < 0 the the current branch of soltutions is unsolvable, turn back
4. has any solution in cache? if so return it.
5. choose a container and make a recursive call to solve subproblem for tanksize = tanksize - container
6. If a solution was found, check if it is the best up to date.

The time analisys is hard, but it takes time proportional to the time needed to fill all solutions. Since the number of solutions will be TankSize/MinContainerSizes, and it does N (container count) operations for it, the complexy will be O(N*TankSize/MinContainerSize).
Space is also O(N*TankSize/MinContainerSize) because of the format of result class.
Java code:

public class TankFill {
	
	private class Result {
		public int[] used;
		public int count;
	}
	
	private int[] containers;
	private Map<Integer, Result> solutions = new HashMap<Integer, Result>();
	
	public int[] fill(int tankSize, int[] containers) {
		this.containers = containers;
		this.solutions = new HashMap<Integer, Result>();
		Result result = fill(tankSize);
		return result == null ? null : result.used;
	}
	
	private Result fill(int tankSize) {
		if (tankSize == 0) {
			Result empty = new Result();
			empty.used = new int[containers.length];
			return empty;
		}
		
		if (tankSize < 0) 
			return null;
		
		if (solutions.containsKey(tankSize)) return solutions.get(tankSize);
		
		Result best = null;
		for (int i=0; i<containers.length;++i) {
			Result next = fill(tankSize - containers[i]);
			if (next != null && (best == null || (next.count+1) < best.count)) {
				best = new Result();
				best.used = next.used.clone();
				best.count = next.count;
				++best.used[i];
				++best.count;
			}
		}
		solutions.put(tankSize, best);
		return best;
	}
}

The fastest and the most easy solution.

/**
 * @author Vishal
 * 
 */
public class TankFillingProblem {

	/**
	 * @author Vishal
	 * 
	 */
	class Answer {
		int[] used;

		Answer(int containers[]) {
			this.used = new int[containers.length];
		}
	}

	/**
	 * @param containers
	 * @param tankSize
	 * @return
	 */
	public Answer calculate(int[] containers, int tankSize) {

		Answer answer = new Answer(containers);

		for (int i = containers.length - 1; i > 0; i--) {
			answer.used[i] = tankSize / containers[i];
			System.out.print("The container " + containers[i] + " is used for "
					+ answer.used[i] + " times.");
			tankSize = tankSize % containers[i];
			System.out.println(" Now we are left with " + tankSize + " tank.");
if (tankSize == 0) {
				break;
			}
		}

		return answer;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TankFillingProblem tfp = new TankFillingProblem();
		tfp.calculate(new int[] { 1, 3, 5, 6, 25 }, 71);
	}

}

Assuming that the list of the container's size is always ordered

function fillTank($tankSize, $containersSize){
    
     $sequence = array();
     while ($tankSize > 0){
         $containerSize = array_pop($containersSize);
         while ($tankSize - $containerSize >= 0) {
             array_push($sequence, $containerSize);
             $tankSize -= $containerSize;
         }
     }
     print_r($sequence);
}

Assuming that the list of container's size is sorted. Substract the maximum container capacity as many times as possible, when it overflows the tank, try with a smaller container, and so on.

function fillTank($tankSize, $containersSize){
    
     $sequence = array();
     while ($tankSize > 0){

         $containerSize = array_pop($containersSize);

         while ($tankSize - $containerSize >= 0) {
             array_push($sequence, $containerSize);
             $tankSize -= $containerSize;
         }
     }

     print_r($sequence);
}

So how do I put this in a flowgorithm flowchart when I have to calculate the number of paint pots needed to paint any size of oil tank (tank has cylindrical side and lid). Diameter is 2 * radius, circumference is 3.14(pi) 8 diameter, area of tank lid 3.14(pi) * radius^ area of tank side height * circumference. Various dimensions can be entered and a statement to say how many pots of paint are needed pleeeease.

void make(int dp[], int a[], int n, int c)
{
    int i, j, min;
    dp[0] = 0;
    for (i=1; i<=c; i++)
    {
        min = dp[i-a[0]];
        for (j=1; j<n; j++)
        {
            if (i-a[j] >= 0)
            {
                if (min>dp[i-a[j]])
                    min = dp[i-a[j]];
            }
        }
        dp[i] = min+1;
    }
}