Question

Recursive backtracking:

Suppose I want to burn some songs onto a 650MB CD (some people still do!) and I have a list of song tracks of various sizes.

I want to fill up as much of my CD as I can. I can use a recursive backtracking strategy to find a subset of the song tracks that optimally fills my CD (that is, with the least space left unfilled). You should recognise this problem as a version of the Knapsack problem.Here is the basic recursive backtracking strategy:

if there are no more songs to consider:

　return solution

else:

　for the next song in the list:
　　try not adding it to the CD, use recursion to evaluate the best solution without it
　　try adding it to the CD, use recursion to evaluate best solution with it
　return the best of these two results as the best solution from here

(a) What should an input instance for this problem consist of?

(b) Given an input instance, what should be returned as a valid solution for the problem?

(c) Given a valid solution, what is the measure to be used to determine if it is better than some other solution?

(d) What basic strategy can be used to prune the recursion tree?

(e) Using your answers to the previous parts of this question as a basis, write down a recursive back-tracking algorithm that solves the CD-fill problem. You can write the code for your algorithm using normal Python syntax, or you can use pseudocode.

Answer 1

This problem is simply a variation of Knapsack problem, In this problem we have different songs of different sizes and we need to accomodate as many songs in a constant size knapsack which is CD of size 650MB here.

a. So the input instance for this problem would be the sizes of the songs which needs to be accomodated in the CD.

b. So as we have the different sizes of the songs, thus we need to output the maximum number of songs we can accomodate in the constant size CD.

c. For checking if the given solution is better, we need to find one other solution where number of songs which are getting accomodated in the CD are more than the current found solution.

d. We can save the sub-solutions in order to not calculate the sub-solutions again and again, this basic strategy is also called as memoization, in which we generally remember the solutions to some problem and if the same problem comes again then we can directly use the saved solution which was calculated previously.

e. Following is the code in python programming.

# Here W is the size of CD left to be filled
# w is the list of song size
# n is the number of songs left to be chosen from
def CD-Fille(W , wt, n): 
    # if no song is there or CD size is empty
    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) 
  
    # return the maximum of two cases: 
    # (1) nth song included so 1 is added
    # (2) not included 
    else: 
        return max( 1+ CD-Fill(W-wt[n-1] , wt, n-1), 
                   CD-Fill(W , wt, n-1)) 
 

IF you have any problem regarding the understanding of the solution, do let me know in the comment section.
Thanks