Algoritmo con Barridos (sweep)

[Kenkox]

Hay un Problema que he pensado bastante pero no se me ha ocurrido una solucion viable. Este problema creo que si los hara pensar un rato

Es este Problema

http://www.cmirg.com:8081/traingate/visualiza.php?usuario=0043a7894053f75f&task=cuentas

En un principio te dan numeros separados por espacios, los 1 significan cuentas de otros colores y los 0 cuentas negras. Tambien como dato te dan el numero de cuentas negras que vas a sacar de ese hilo. Lo que se tiene que hacer es encontrar el menor numero de cuentas que tienes que sacar para poder tener el numero de cuentas negras dadas por el usuario.

001001010101

Digamos que el usuario quiere sacar 4 cuentas negras... el numero minimo que debe de sacar es 1... ya que puedo tomar directamente las 2 del primer extremo, saco una cuenta de color y encuentro otras 2 cuentas negras libres.....

Todo viene mejor explicado en el link anterior.

Mi idea de resolucion es primero tomar las cuentas de los extremos( siempre y cuando haya ).. despues, empezar a contar de un primer extremo hasta tener las cuentas negras deseadas... y obviamente llevar la cuenta de las cuentas de colores.... y hacer lo mismo con el otro extremo......y despues comparar quien tenga menos cuentas de colores... el problema es que no creo que esta solucion resuelva todos los casos posibles para ese problema.... ya que segun yo pueden existir una infinidad de casos en los que mi programa siguiendo mi "algoritmo", de una solucion erronea...

Asi que les queria pedir ayuda para ver si son tan amables de dar "ideas" para la resolucion del problema. Por cierto, el programa se hace en c++,c o pascal, pero no me quiero meter ahorita con el lenguaje, solo quiero terminar el algoritmo mas viable...

Otra solucion que se me ocurrio fue ir contando los 0's hasta encontrar un 1, apartir de ahi, ver cuantos 1's existen y despues contar cuantos ceros existen en ese lugar.... hacer lo mismo en el otro extremo y apartir de saber cuantos 1's existen y e numero de 0's , tomar la decision de hacia que extremo continuar. PEro igual veo varias deficiencias.

De antemano muchas gracias

[crozz2]

No se si sepas utilizar arboles, la idea que se me ocurre es esta:

Generar un arbol que como raiz tenga la cadena entera, luego generar una rama por cada posibilidad, es decir, una nueva rama para sacar del lado derecho y otro nueva para el lado izquierdo e ir haciendo eso con cada rama nueva generada, al final que regrese el camino de la ruta con menos coste, te dejo una imagen con la idea:

http://s2.subirimagenes.com/privadas/previo/thump_2071344capturaarbol.png

Espero te guste la idea, me avisas

http://javatap1.blogspot.mx/