lundi 26 janvier 2015

Looking for a DP algorithm for a specific packing problem


I have the following problem to solve:


Given a ferry with length d and a list of n cars conataining their length we must load the cars on the ferry in an order in which they appear in the list on 2 different lanes (each one having length d). Write a program that given length d and the list of cars outputs maximal number of cars that can be loaded on the ferry.


It's quite easy to do in O(2^cars) with backtracking - we load car on the left and try all the possibilities then, we save maximum and load car on the right and do the same saving max again.


But I have a feeling this can be reduced to polynomial time with dynamic programming. How to tell whether my gut feeling is true?





Aucun commentaire:

Enregistrer un commentaire