Confusion with memoization

Consider the following function that generates a sparse diagonal Matrix

W[n_] := W[n] = Exp[(2 Pi I)/n]//N;  Clear[X];  X[n_, L_, power_ : 1][i_, chain_] := X[n, L, power][i, chain] = DiagonalMatrix@SparseArray@Table[ W[n]^(-IntegerDigits[a,n,2 L][[chain*L-i+1]]power), {a, 0,n^(2 L)-1}] 

Due to the f[x_]:=f[x]=SlowFunction definition, I expect this code to be much faster on a second run. If I evaluate the following on my laptop several times

X[3, 7][1, 1] // Timing 

I get $ 12$ seconds on the first run then around $ 2.8$ seconds on any evaluation after that. Clearly the memoization trick seems to have made this faster, but it is still much slower than it should be. For example if I run

a = X[3, 7][1, 1] 

then

a //Timing 

I get $ 10^{-6}$ seconds. Running X[3, 7][1, 1] the second time should also be this fast, since the matrix is already computed and saved. But it seems that instead it is still doing some computation. Any reason this happens?

0/1 Knapsack algorithm with memoization slow (C#) [closed]

I’m solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.


Problem statement

There are N items, numbered 1,2,ā€¦,N. For each i (1ā‰¤iā‰¤N), Item i has a weight of wi and a value of vi

Taro has decided to choose some of the N items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W

Find the maximum possible sum of the values of items that Taro takes home.


The input is in the following form:

N W w1 v1 w2 v2 : wN vN 

N: Number of items.

W: Max weight I can have.

wi: ith weight.

vi: ith value.

Here is my solution to it:

using System; using System.Collections.Generic;  public static class Solution {   // Both s_weights and s_values will have the same length.   private static int[] s_weights; // array holding the weights of the items.   private static int[] s_values; // array holding the values of the items.   private static Dictionary<(int, int), long> s_memo; // memoization dictionary.    // NOTE: I cannot use an array instead of a dictionary here, cause it   // will be a very large 2d array and will give OutOfMemoryException.    public static void Main()   {     // Read the first line, which contains number of items and max weight.     string[] nw = Console.ReadLine().Split(' ');     // Parse n.     int n = int.Parse(nw[0]);     // Parse the max weight.     int maxWeight = int.Parse(nw[1]);      s_weights = new int[n];     s_values = new int[n];     // arbitrary high capacity dictionary to avoid resizing which is O(n).     s_memo = new Dictionary<(int, int), long>(10000000);      // Read each line from the input.     for (int i = 0; i < n; i++)     {       string[] wv = Console.ReadLine().Split(' ');       s_weights[i] = int.Parse(wv[0]);       s_values[i] = int.Parse(wv[1]);     }     // Start the recursion with the maximum weight and all the items.     Console.WriteLine(Solve(maxWeight, n));   }    private static long Solve(int weightLeft, int numberOfItemsToConsider)   {     // simple base case.     if (weightLeft == 0 || numberOfItemsToConsider == 0) return 0;      // If already calculated, get it from the dictionary.     if (s_memo.TryGetValue((weightLeft, numberOfItemsToConsider), out var cachedValue))     {       return cachedValue;     }      // Recursive call calculating the solution if we don't take the current item.     long dontTakeCurrent = Solve(weightLeft, numberOfItemsToConsider - 1);     long result;      // Can we take the current item? If yes, calculate the solution.     if (weightLeft >= s_weights[numberOfItemsToConsider - 1])     {       long takeCurrent = s_values[numberOfItemsToConsider - 1] + Solve(weightLeft - s_weights[numberOfItemsToConsider - 1], numberOfItemsToConsider - 1);       // Maximize the value between the two cases, taking or not taking the item.       result = Math.Max(takeCurrent, dontTakeCurrent);       // Add the result to the memo dictionary.       s_memo.Add((weightLeft, numberOfItemsToConsider), result);       return result;     }     // Here, we don't have another choice other than not taking the item.     result = dontTakeCurrent;     s_memo.Add((weightLeft, numberOfItemsToConsider), result);     return result;   }                           } 

Note: I’ve already asked the question in codereview but no answer until now, so I thought cs could be a better place to ask about it.

Can memoization be applied to any recursive bottom up algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming.

I am having a hard time understanding if at all I can apply memoization to a particular recursive bottom up algorithm and if there is a relation between memoization being applicable ONLY to top down recursive algorithms. Any explanation on the same would be greatly appreciated.

The Background to this question:

I have a naive inefficient bottom up recursive solution(below) a and wish to incorporate memoization but don’t know if it is possible.

Problem Statement: Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, Print the number of ways (non-distinct sets) this can be achieved.

Ex: Ex: N = 4 , S = {1, 2, 3}  1 1 1 1  1 1 2  1 2 1  1 3  2 1 1  2 2  3 1  

My code:

public static int change(int n, int count, int sum) {          if(sum == n) {             return 1;         }         if(sum > n) {             return 0;         }         for(int i = 1; i <=3; i++) {             sum = sum + i;             count += change(n, 0, sum);             sum = sum - i;         }         return count;     } 

a recursive function using memoization

I have looked at a lot of these cases, e.g. Can one identify the design patterns of Mathematica? and the included ones.

My trimmed example, here establishing the ‘initial conditions’ (where the zp___List symbol has 3 underscores) and utilizes only 2 external global functions, B and K;

wgn[0,0,zp___List]:=0; wgn[0,1,zp___List]:=0; wgn[0,2,zp___List]:=B; wgn[g_Integer/;g<0,npo_Integer,zp___List]:=0; wgn[g_Integer,npo_Integer/;npo<0,zp___List]:=0; 

and then the recursion (I changed a double sum to a Sum @@ Flatten[Table[);

wgn[g_Integer /; g >= 0, npo_Integer?Positive, zp___List] :=    wgn[g, npo, zp] =    (     Sum[      (       Module[{z, tmp1, tmp1b, tmp2, asso, T1},          tmp1 = Rest[Drop[zp, -Length[zp]/2]];         tmp1b = Rest[Drop[zp, Length[zp]/2]];         tmp2 = Subsets[tmp1, {0, npo - 1}];         asso = AssociationThread[tmp1, tmp1b];                        T1 = Table[{tmp2[[o]], Complement[tmp1, tmp2[[o]]]}, {o, 1,            Length[tmp2]}];         (           wgn[g - 1, npo + 1, Flatten[List[Join[                {z, -z},                Rest[Drop[zp, -Length[zp]/2]],                {j, j},                Rest[Drop[zp, Length[zp]/2]]]               ]]]             +             Total[Flatten[Table[                wgn[h, 1 + Length[T1[[wc]][[1]]],                  Flatten[                  List[Join[{z}, T1[[wc]][[1]], {j},                     asso /@ T1[[wc]][[1]]]]]]                *                 wgn[g - h, 1 + Length[T1[[wc]][[2]]],                  Flatten[                  List[Join[{-z}, T1[[wc]][[2]], {j},                     asso /@ T1[[wc]][[2]]]]]]               , {h, 0, g}, {wc, 1, Length[T1]}]]]            )         , {z, 0}]        ]       )      , {j, 1, 1}]     ); 

tmp1 & tmp1b split the 3rd argument into variables and numbers and there is an association – asso – between them. So the 2nd variable and 2nd number are correlated. tmp2 calculates all the Subsets of $ $ z_1,\ldots,z_n$ $ and then T1 constructs pairs where one element of tmp2 at a time is paired with its set-complement, i.e. to make $ $ A \cup B = \{1,\ldots,n\}$ $ , and then summed over in the double sum.

I call it like,

wgn[2,1,{z01,1}] 

and for this case expect

wgn[1,2,{z,-z} + w[0,1,{z,j}]*w[2,1,{-z,j}] + w[1,1,{z,j}]*w[1,1,{-z,j}] + w[2,1,{z,j}]*w[0,1,{-z,j}] 

where j would be 1 by the double sum… I mean the Sum @@ Flatten[Table[.... Then the 2 ‘initial conditions’ would fill in the rest, giving (after killing the w[0,1,{...}] terms,

wgn[1,2,{z,-z} + w[1,1,{z,j}]*w[1,1,{-z,j}]  

Then the recursion would start again, and the w[1,1,{z01,1}] terms would be replaced by,

~ Res[K*w[0,2,{z,-z,j,j}],{z$  2,0}] 

and the wgn[1,2,{z,-z}] term replaced by some other terms.

Problem now is that I have the recursion limit problem but can’t figure out why, especially since my initial conditions should take care of any runaway negative valued terms.

(One thing, the 2nd variable, npo is half the length of the list zp.)

Here is the formula if it is at all needed,

$ $ w_{g,n+1}^{i_0,i_1,\ldots,i_n}(z_0,z_1,\ldots,z_n) \sim \sum_{j=1}^N Res_{z->0} K * \left( w_{g-1,n+2}^{j,j,i_1,\ldots,i_n}(z,-z,z_1,\ldots,z_n) + \sum_{A\cup B=\{1,\ldots,n\}} \sum_{h=0}^g w_{h,1+|A|}^{j,\vec{i_A}}(z,\vec{z_A}) * w_{g-h,1+|B|}^{j,\vec{i_B}}(-z,\vec{z_B}) \right)$ $

I define npo := n+1. The function Res is just residue but returning zero isn’t too helpful šŸ˜‰

Recursive knapsack with memoization not behaving as expected

Disclaimer: I’m aware there are kinda similar questions already answered over the Internet but I’m willing to find someone who can help me understand why my code in particular is not working. I’m glad if you can help me! šŸ™‚

Task: Write a function that given an array of items ([weigth, value]) and a limit capacity, returns the largest value possible so that the total weight is less than or equal to the given limit.

Problem: I’m having problems implementing memoization, I’m kinda stuck… Without memoization the code seems to work. With the implementation of memoization the code give wrong results. Can you kindly help me identify my problem?

Code:

const knapsack = (items, capacity) => {      // number of items * capacity memoization matrix     let m = [...Array(items.length)].map(_ => [...Array(capacity)])      // helper function for recursion     const recursion = (items, capacity) => {          // memoization query         if (m[items.length - 1][capacity - 1])             return m[items.length - 1][capacity - 1]          // base case         if (items.length <= 0 || capacity <= 0)             return 0          let weight, value, rest         let result = 0         let best = 0          // loop through all the given items         for (let i = 0; i < items.length; i++) {              // deconstruct items into weight and value variables             [weight, value] = items[i]              // remove current item to avoid picking an item twice             rest = [...items]             rest.splice(i, 1)              // if there is space go down the recursion             if (weight <= capacity)                 result = value + recursion(rest, capacity - weight)              if (best < result)                 best = result         }          // save the best result into m         m[items.length - 1][capacity - 1] = best         return best     }      // initial call of recursion     return recursion(items, capacity) } 

Some inputs:

test1: {   items: [     [3,2],      [2,1],      [4,4],      [1,1]   ]   capacity: 5 }  test2: {   items: [     [4,5],      [1,8],      [2,4],      [2,5],      [2,3]   ]   capacity: 10 } 

Knapsack problem – recursive approach with memoization

This post is based on the 0-1 Knapsack problem. I came across this problem in Assignment #4 of Professor Tim Roughgarden’s course Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming on Coursera.

Question 1:

In this programming problem and the next you’ll code up the knapsack algorithm from lecture.

Let’s start with a warm-up. Download the text file below.

knapsack.txt

This file describes a knapsack instance, and it has the following format:

[knapsack_size][number_of_items]

[value_1] [weight_1]

[value_2] [weight_2]

For example, the third line of the file is “50074 659”, indicating that the second item has value 50074 and size 659, respectively.

You can assume that all numbers are positive. You should assume that item weights and the knapsack capacity are integers.

In the box below, type in the value of the optimal solution.

My program:

def knapSack(W , wt , val , n):       # Base Case      if n == 0 or W == 0 :          return 0     # If weight of the nth item is more than Knapsack of capacity      # W, then this item cannot be included in the optimal solution      if (wt[n-1] > W):          return knapSack(W , wt , val , n-1)      # Check for required value in lookup table first     if (lookup[n][W]!=-1):         return lookup[n][W]          # Add to lookup table and return the maximum of two cases:      # (1) nth item included      # (2) not included      else:          x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))         lookup[n][W] = x         return x  #End of function knapSack   #To test above function  val = [] wt = [] with open("knapsack.txt") as f:     first_line = f.readline().split()     W = int(first_line[0])     n = int(first_line[1])     for line in f:       words = line.split()       val.append(int(words[0]))       wt.append(int(words[1]))  lookup = [[-1 for i in range(W+1)] for j in range(n+1)] print knapSack(W, wt, val, n)  

This program gave me the output as 2493893, which matches with the official solution. So I presume that my code is correct. So far so good. The next question in the same assignment is as follows.

Question 2:

This problem also asks you to solve a knapsack instance, but a much bigger one.

Download the text file below.

knapsack_big.txt

This file describes a knapsack instance, and it has the following format:

[knapsack_size][number_of_items]

[value_1] [weight_1]

[value_2] [weight_2]

For example, the third line of the file is “50074 834558”, indicating that the second item has value 50074 and size 834558, respectively. As before, you should assume that item weights and the knapsack capacity are integers.

This instance is so big that the straightforward iterative implemetation uses an infeasible amount of time and space. So you will have to be creative to compute an optimal solution. One idea is to go back to a recursive implementation, solving subproblems — and, of course, caching the results to avoid redundant work — only on an “as needed” basis. Also, be sure to think about appropriate data structures for storing and looking up solutions to subproblems.

In the box below, type in the value of the optimal solution.

My program (same as before):

def knapSack(W , wt , val , n):       # Base Case      if n == 0 or W == 0 :          return 0     # If weight of the nth item is more than Knapsack of capacity      # W, then this item cannot be included in the optimal solution      if (wt[n-1] > W):          return knapSack(W , wt , val , n-1)      # Check for required value in lookup table first     if (lookup[n][W]!=-1):         return lookup[n][W]          # Add to lookup table and return the maximum of two cases:      # (1) nth item included      # (2) not included      else:          x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))         lookup[n][W] = x         return x  #End of function knapSack   #To test above function  val = [] wt = [] with open("knapsack_big.txt") as f:     first_line = f.readline().split()     W = int(first_line[0])     n = int(first_line[1])     for line in f:       words = line.split()       val.append(int(words[0]))       wt.append(int(words[1]))  lookup = [[-1 for i in range(W+1)] for j in range(n+1)] print knapSack(W, wt, val, n)  

The second question had mentioned that the ordinary iterative approach would not suffice and that we’d have to get back to the recursive approach and use appropriate caching. Fair enough. I had already used the recursive approach in my initial program and also implemented a lookup table for memoization purposes.

It worked perfectly fine on the smaller data set i.e. knapsack.txt and took less than a second to execute. However, when I execute the program on the second file knapsack_big.txt (which is considerably larger than knapsack.txt) it takes forever to execute and in most cases ends up getting killed.

So, any idea how to speed up the program so that it can be executed on larger data sets? I suspect that there might be more efficient data structures (than a simple 2D list) for this problem, but not sure which.