Problema de asignación---algoritmo para dividir ocho libras de vino en dos partes iguales
Encuentre la solución óptima al problema C de la división del vino de Poisson.
/*
Diseñe un programa para resolver el "problema de la división del vino de Poisson"
El problema es el siguiente:
Una persona tiene una botella de cerveza de 12 pintas y quiere sacar 6 pintas de ella, pero no tiene un recipiente de 6 pintas. ,
sólo un envase de 8 pintas y un envase de 5 pintas, ¿cómo puedo dividir la cerveza en dos envases de 6 pintas?
Análisis abstracto:
b = contenedor grande, también representa volumen
s = contenedor pequeño, también representa volumen
(f) , (h), (e) estado f=lleno, e=vacío, h=número, indicando capacidad
Operación 1: b(f) - s(e) =gt; ), s(f)
Variación b(h) - s(e) =gt; b(h - s), s(f)
Operación 2: b( e ) s(f) =gt; b(s), s(e)
Variación b(h) s(f) =gt; b(f), s(s - b h)
Derivación b(f) - s(h)
b(h) - s(h)
b(e) s(h)
b(h) s(h)
Si se utiliza como nodo el número de vino que hay en la botella, los nodos se pueden considerar conectados a través de más de una operación.
Esta pregunta se puede transformar en un problema de búsqueda de un gráfico dirigido.
Es decir, encontrar la ruta mínima entre los nodos especificados (12, 0, 0) y (6, 6, 0).
*/
#include lt;cstdiogt;
#include lt;dequegt;
#include lt;mapgt;
#include lt;utilitygt;
#include lt;queuegt;
static int big_max_value[] =
{
12, 8, 12
};
static int small_max_value[] =
{
8, 5, 5
};
static const int big_offset[] =
{
0, 1, 0
};
static const int small_offset[] =
{
1, 2, 2
};
//Definición de nodo
clase Nodo
{
unsigned char mBig
unsigned char mMid
char unsigned mSmall
público:
static void InitMaxValue(int max1, int max2, int max3)
{
big_max_value[ 0] = max1 ;
big_max_value[1] = max2;
big_max_value[2] = max1;
small_max_value[0] = max2;
valor_máximo_pequeño[1
] = max3;
small_max_value[2] = max3;
}
Nodo(): mBig(0), mMid(0), mSmall(0 )
{
}
Nodo (carácter a sin firmar, carácter b sin firmar, carácter c sin firmar): mBig(a), mMid(b), mSmall (c)
{
}
enum OPCODE
{
BIG_OP_MIDDLE = 0,
MIDDLE_OP_SMALL,
BIG_OP_SMALL,
OP_LAST
};
//Operación de resta
void sub(OPCODE op)
{
int big_max = big_max_value[op];
int small_max = pequeño_max_value[op];
charamp; grande = *(reinterpret_castlt; char*gt; (este) big_offset[op]);
charamp; pequeño = *(reinterpret_castlt; char*gt; (este) pequeño_offset[op]);
if (gt grande; (small_max - pequeño))
{
grande -= (small_max - pequeño);
pequeño = pequeño_max;
}
else
{
pequeño = grande;
grande = 0;
}
}
//Agregar operación
void add(OPCODE op)
{
int big_max = big_max_value[op];
int small_max = pequeño_max_value[op];
charamp big = *(reinterpret_castlt;char*gt;(this) big_offset [op]);
charamp; pequeño = *(reinterpret_castlt; char*gt; (este) pequeño_offset[op]);
if (pequeño gt; big_max - grande)
{
pequeño -= big_max - grande;
grande = big_max;
}
más
p>
{
grande = pequeño;
pequeño = 0
}
}<; /p>
bool check(valor int)
{
if (mBig == valor || mMid == valor || mSmall == valor)
{
devuelve verdadero;
p>
}
devuelve falso;
}
void print() const
{
printf("estado [d]=2d, [d]=2d, [d]=2dn", big_max_value[0], mBig, big_max_value[1], mMid,
small_max_value[2], mSmall);
}
//Determinación de igualdad
friend bool operator==(Node const amp; a, Node const amp; b)
{
return memcmp(amp; a, amp; b, sizeof(Node)) ==
}
operador bool amigo; lt; (Const de nodo amp; a, Const de nodo amp; b)
{
return memcmp(amp; a, amp; b, sizeof(Node)) lt;
}
};
plantilla lt; clase Tgt;
búsqueda vacía (T inicio, valor int)
{
typedef std::pairlt;T, NodeValueType;
typedef std::maplt;T, Tgt;
typedef; NodeSet::iterator NodeSetIter;
typedef std::queuelt;NodeValueType, std::dequelt;NodeValueTypegt;gt;NodeQueue;
NodeSet visitado;
NodeQueue searchQueue;
NodeValueType último;
searchQueue.push(std::make_pair(start, start));
while (!searchQueue.empty() )
{
NodeValueType cur = searchQueue.front();
searchQueue.pop()
visited.insert(cur ) ;
if (cur.first.check(value))
{
último = cur;
break;
p>
}
for (int i = 0; i lt; Nodo::OP_LAST; i)
{
Nodo next1 = cur primero;
next1.sub(static_castlt;Node::OPCODEgt;(i));
if (visited.find(next1) == visited.end( ))
p>
{
searchQueue.push(std::make_pair(next1, cur
.first));
}
Nodo next2 = cur.first;
next2.add(static_castlt;Node::OPCODEgt;(i));
if (visitado.find(siguiente2) == visitado.end())
{
searchQueue.push(std::make_pair(siguiente2, cur .first));
}
}
}
NodeSetIter cur = visitado.find(last.first);
} p>
mientras (!(cur-gt; primero == inicio))
{
cur-gt;
cur = visitado.find(cur-gt; segundo);
}
cur-gt;primero.print();
}
int main()
{
puts("Alguien tiene una botella de 12 pintas de cerveza y quiere sacar 6 pintas de ella , pero no tiene 6 pintas n"
"Solo hay un recipiente de 8 pintas y uno de 5 pintas, ¿cómo se puede dividir la cerveza en dos recipientes de 6 pintas n");
for (int i = 0; i lt; 12; i)
{
printf("---Encuentra los pasos mínimos para obtener d pintas, en orden inverso----- -------n", i);
Buscar(Nodo(12, 0, 0), i);
}
puts ("Otra solución es un recipiente n con 13 pintas de cerveza, un recipiente de 9 pintas y un recipiente n de 5 pintas");
Node::InitMaxValue( 13, 9, 5);
for (int i = 0; i lt; 12; i)
{
printf("---Buscar los pasos mínimos para obtener d pintas, en orden inverso-- ----------n", i);
Search(Node(13, 0, 0), i);
}
return 0;
}
De hecho, el último paso, el resultado debería ser (6, 6, 0 ) pero de hecho solo logro la situación en la que aparece un 6. La razón Pero no todos los resultados tienen dos valores idénticos La siguiente es la solución óptima que hice para 12, 8 y 5:
Alguien tiene. una botella de 12 pintas de cerveza y quiere servir 6 pintas, pero no tiene un recipiente de 6 pintas, solo uno de 8 pintas y uno de 5 pintas, ¿cómo puede dividir la cerveza en dos? ¿Envases de 6 pintas?
---Encuentra los pasos mínimos para obtener 0 pintas, en orden inverso------------
status [12]=12, [8 ]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 1 pinta, en orden inverso------------
estado [12] = 1, [8] = 8, [5] = 3
estado [12] = 9, [8] = 0, [5] = 3
estado [12] = 9, [8] = 3, [5] = 0
estado [12] = 4, [8] = 3, [5] = 5
estado [12] = 4, [8] = 8, [5] = 0
p>
estado [12]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 2 pintas, en orden inverso----- -- -----
estado [12]= 2, [8]= 5, [5]= 5
estado [12]= 7, [8]= 5, [5]= 0
estado [12]= 7, [8]= 0, [5]= 5
estado [12]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 3 pintas, en orden inverso------------
estado [ 12]= 4, [8]= 3, [5]= 5
estado [12]= 4, [8]= 8, [5]= 0
estado [ 12]=12 , [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 4 pintas, en orden inverso------------
estado [12]= 4, [8]= 8, [5]= 0
estado [12]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 5 pintas, en orden inverso-----------
estado [12]= 7, [8 ]= 0, [5]= 5
estado [12]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 6 pintas, en orden inverso---- --------
estado [12]= 1, [8]= 6, [5]= 5
estado [12]= 1, [8] = 8, [5]= 3
estado [12]= 9, [8]= 0, [5]= 3
estado [12]= 9, [8] = 3, [5]= 0
estado [12]= 4, [8]= 3, [5]= 5
estado [12]= 4, [8] = 8, [5]= 0
estado [12]=12, [8]= 0, [5]= 0
---Encuentra el número mínimo de 7 pintas Pasos, orden inverso------------
estado [12]= 7, [8]= 0, [5]= 5
estado [12 ]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 8 pintas, en orden inverso-- ----------
estado [12]= 4, [8]= 8, [5]= 0
estado [12]=12, [ 8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 9 pintas, en orden inverso------------
estado [12]= 9, [8]= 3, [ 5]= 0
estado [12]= 4, [8]= 3, [5]= 5
estado [12]= 4, [8]= 8, [ 5]= 0
estado [12]=12, [8]= 0, [5]= 0
---Encuentra los pasos mínimos para obtener 10 pintas, en orden inverso- -----------
estado [12]=10, [8]= 2, [5 ]= 0
estado [12]= 5, [8]=2,[
5]= 5
estado [12]= 5, [8]= 7, [5]= 0
estado [12]= 0, [8]= 7, [ 5]= 5
estado [12]= 7, [8]= 0, [5]= 5
estado [12]=12, [8]= 0, [ 5]= 0
---Encuentra los pasos mínimos para obtener 11 pintas, en orden inverso------------
estado [12]= 11, [8]= 0, [5]= 1
estado [12]= 3, [8]= 8, [5]= 1
estado [12]= 3, [8]= 4, [5]= 5
estado [12]= 8, [8]= 4, [5]= 0
estado [12]= 8, [8]= 0, [5]= 4
estado [12]= 0, [8]= 8, [5]= 4
estado [12]= 4, [8]= 8, [5]= 0
estado [12]=12, [8]= 0, [5]= 0
Tenga en cuenta que esta solución es muy versátil, también puedes resolver otras combinaciones: como las últimas 13, 9, 5.