Soy un estudiante universitario de informática que trabaja en un proyecto. En mi proyecto tengo un problema de optimización, que creo que se puede resolver de manera óptima con un algoritmo codicioso. En todos los casos que he examinado, el algoritmo codicioso da la solución óptima, así que estoy bastante convencido de que siempre lo hará. Me gustaría demostrar matemáticamente que este es siempre el caso.
Para dar un poco de contexto, he aquí el problema explicado.
Dados dos conjuntos múltiples, A y B que sólo contiene números enteros positivos, y el valor objetivo m . Construir el mínimo número de submultisets que contengan como máximo un miembro de B y cualquier número de miembros de A y cada submultiset tiene una suma <= m . Tenga en cuenta que cada miembro de A y B sólo puede utilizarse una vez.
Ejemplo ingenuo: A {3, 3, 4, 5, 8}, B {2, 5}, m \= 10
Solución: {5,5}, {2,8}, {3,3,4}
El algoritmo codicioso toma el valor más alto en B calcula el conjunto de potencias de A y elige el subconjunto de A , subconjuntoA con lo que se obtiene suma máxima ( subconjuntoA + Bmax ) <= m . A continuación, eliminar subconjuntoA y Bmax de A y B y hacer esto una y otra vez hasta que ambos conjuntos estén vacíos.
Dado que el objetivo es vaciar los conjuntos, la lógica que subyace al algoritmo es simplemente eliminar el subconjunto más grande (en términos de suma) posible de A una y otra vez, emparejado con un miembro de B una y otra vez.
Yo estudiando informática, significa que la formación matemática no es la más fuerte. ¿Qué técnicas se utilizarían para demostrar que el ejemplo anterior da la solución óptima al problema (menor número de subconjuntos)? Cualquier ayuda es apreciada, ya que estoy un poco atascado en este caso.
