Strange Docs

Unbounded Knapsack : Given a knapsack weight W and a set of N items with certain value Vi and weight W i , we need to calculate minimum amount that could make up this quantity exactly. To have a more clear understanding of this problem, see SPOJ-PIGBANK Sample Problem : We're given a box which can hold maximum W weight. There are N various coins each of value Vi and Weight Wi. We need to fill the box with total W weight with any number of coins of any value. Note that coins are unlimited.  100 ----- W 2 ------- N 1 1 ----- vi,wi 30 50 --- vi,wi Answer of the problem above is, 60. If we take 2 coins of value 30, weight 50, we'll get exactly weight 100 with a minimum value of 60. Algorithm : This is a DP solution. To get the solution for W=100, we'll solve subproblems first. Let dp[W+1]  be an array which will store the subproblems solutions. In the end, dp[W] will give us the minimum amount. Subproblems soultion will be the minimum of taking the coin Vk ...

Given an arbitrary series, we've to calculate the maximum sum confined to only one restriction- If we choose any number a [ i ] to calculate the sum, we can't choose a [ i+1 ] Let's take a series: a[ ]= {1,2,3,4,5,9} Linear Solution: Take two variable inc and exl . inc will store value if we choose a [ i ] to calculate the sum & exl will store value if we do not choose a [ i ], for any 0 ≤ i ≤ n. Now for every step, we have to calculate inc and exl . After iteration ends, max( inc,exl ) is the maximum non-contiguous sum. Roughly- Why inc = exl + a [ i ] ? because the already calculated exl is from i-2 . So if we choosed inc=  inc + a [ i ] , that would be a contiguous sum . exl is maximum of inc & exl right until   i-1 . Top Down solution( DP ): If you're familiar with dynamic programming, you know that, we need to calculate dp[n] - the maximum non contiguous sum at nth index. Now we can have two possible state, we'll select the maximum ...

Imagine a climber trying to climb on top of a wall.  A wall is constructed out of square blocks of equal size. From each block, the climber can reach three blocks of the row right above: one right on top, one to the right and one to the left ( unless right or left not available because that is end of the wall ). Find the least costly path from bottom to top where cost is the summation of costs of the blocks used on the path. Problem Representation: An NxM size grid where each cell has a positive cost C(i,j) associated with it. There exists three possible moves from a cell (i,j) - i+1,j-1     [ diagonally left ] i+1. j       [ above ] i+1.j+1     [ diagonally right ] Take an array dp[ n ][ m ] that will hold the cost for all cells. Initiate dp[ 0 ][ i ] = C(0,i)  for 0 ≤ i ≤ m . There are three cases to the recurrence: a cell might be in the middle (horizontally), on the leftmost or  on ...

Problem Statement As from the problem-tag, you can see this is a DP( Dynamic Programming ) problem. Don't know Dynamic Programming? Here are some articles: Codechef , TopCoder . Try to solve a sample problem, for example, Fibonacci Numbers. Let's start cracking the problem. To solve a DP problem, the hardest and important part is to find the relation between previous or next steps and current step . We need to find out how the solution of the current step depends on its previous steps or next steps. Looking at:      2 5 1 1 4        from left to right Step 1: You can only interpret this as 2(B). Decoding- B EAAD  So, DP[1] = 1 Step 2: This can be 5(E) or collaborating with 2, it can be 25(Y). Result is BE AAD + Y AAD . So, DP[2] = 2 Step 3: Can only be interpreted as 1(A). 51 is not valid, as stated in problem. BEA AD + YA AD . DP[3] = 2.  Step 4: Will be interpreted as 1(A). BEAA D + YAA D+... ...