Ayúdame a llevar mis bolsas de compras

26

Era una cálida tarde de verano ...

cuando mi estúpido auto decidió descomponerse en el medio de la carretera al regresar del supermercado. Lo empujé a un lado y decidí caminar a casa. Abrí el maletero para sacar la comida y las cosas restantes. Fue entonces cuando noté que los artículos no estaban empacados de manera uniforme. Algunas bolsas tenían artículos más pesados, mientras que otras tenían pocas cosas más livianas, algunas incluso tenían una mezcla de tales artículos. Para facilitarme el transporte, decidí agrupar todo en dos bolsas y hacer que sus pesos fueran lo más cercanos posible.

estoy yendo al centro

Tu meta

es para ayudarme a reorganizar los artículos en dos bolsas de compras de tal manera que la diferencia entre ambas bolsas sea lo más cercana posible a cero.
Matemáticamente:

PESO A LA IZQUIERDA - PESO A LA DERECHA ≈ 0

Ejemplo

Si solo tuviera 2 artículos, pan y mantequilla de maní, y el peso del pan es de 250 gramos y la mantequilla de maní es de 150 gramos, la mejor manera es llevarlos por separado en dos manos.

W LH - W RH = W (PAN) - W (P.BUTTER) 250-150
= 100

La otra posibilidad es:

W (PAN, MANTEQUILLA) - W (mano vacía) = (250 + 150) - 0 = 400

Esto no es mejor que nuestro primer caso, por lo que debe ir con el primero.

Su código debe

  1. tome entradas de números que indiquen el peso de los artículos en la bolsa de compras. Las unidades no son importantes, pero deberían ser las mismas (idealmente kilogramos o gramos). La entrada se puede hacer uno por uno o todos a la vez. Puede restringir el recuento total a 20 artículos como máximo, si lo desea.
  2. El formato / tipo de entrada depende de usted para elegir, pero no debe estar presente nada más que los pesos.
  3. Se permite cualquier idioma, pero se adhieren a las bibliotecas estándar.
  4. Salida de pantalla. Nuevamente, puedes elegir el formato, pero explica el formato en tu publicación. es decir, cómo podemos saber cuáles son los elementos de la mano izquierda y cuáles son los elementos de la mano derecha.

Puntos

  1. El código más corto gana.

Insinuación

Los dos algoritmos posibles en los que podría pensar son la diferenciación (más rápido) y las permutaciones / combinaciones (más lento). Puede usar estos o cualquier otro algoritmo que haga el trabajo.

Renae Lider
fuente
55
Me gusta la regla 2, es flexible pero no permite trampas
edc65
2
Básicamente has reinventado el problema de la mochila. en.wikipedia.org/wiki/Knapsack_problem
Sparr
Gracias @Sparr Soy malvada (no realmente)
Renae Lider
2
Este problema es demasiado práctico y realista para este sitio.
Restablece a Monica iamnotmaynard el

Respuestas:

15

Pyth, 9 bytes

ehc2osNyQ

Entrada, formatos de salida:

Input:
[1, 2, 3, 4, 5]
Output:
[1, 2, 4]

Demostración.

ehc2osNyQ
             Q = eval(input())
       yQ    Take all subsets of Q.
    osN      Order those element lists by their sums.
  c2         Cut the list in half.
eh           Take the last element of the first half.

Esto funciona porque ydevuelve los subconjuntos en un orden tal que cada subconjunto y su complemento son equidistantes del centro. Como la suma de un subconjunto y la suma de su complemento siempre serán equidistantes del centro, la siguiente lista osNyQtambién tendrá esta propiedad. Por lo tanto, los dos elementos centrales osNyQson complementos y deben tener una división óptima. Extraemos el primero de esos dos elementos y lo imprimimos.

isaacg
fuente
La respuesta del OP solo imprime las bolsas en una mano, así que felicidades por su solución de 9 bytes.
Dennis
Su escritura tiene errores para la entrada [7 7 7 10 11] Rastreo (última llamada más reciente): Archivo "pyth.py", línea 772, en <module> Archivo "<string>", línea 4, en <module> Archivo "/app/macros.py", línea 865, en orden TypeError: tipos no ordenados: int () <list ()
RosLuP
@RosLuP Esto funcionó en ese momento, cambié algo al respecto sque hizo que dejara de funcionar. A la gente no le gustó el cambio, y tu comentario fue el empujón final que necesitaba para cambiarlo.
isaacg
En el código comentado no debe ser "subconjunto de Q" sino "sublista de Q"
RosLuP
@RosLuP No estoy de acuerdo: una sublista suele ser contigua. Subconjunto y subsecuencia son dos términos para este tipo de cosas.
isaacg
6

Pyth, 16

ho.a-FsMNs./M.pQ

Esto toma las entradas como una lista pitónica en STDIN. La salida es una lista de 2 listas, siendo la primera lista los artículos en una bolsa y la segunda lista representa los artículos en la segunda bolsa. Este bruto fuerza todas las combinaciones, por lo que se ejecutará muy lentamente (o se quedará sin memoria) para entradas grandes.

Pruébalo en línea aquí

Para admitir el manejo de una sola entrada, esto sube a 17:

hho.a-FsMNs./M.pQ

Esto imprimirá los valores que van en una mano.

FryAmTheEggman
fuente
Esta es una solución muy impresionante: no es obvio en absoluto que no dará respuestas incorrectas [[2], [1], [1]], pero creo que funciona, debido exactamente a cómo ./funciona.
isaacg
En realidad, creo que esto falla en los casos en que todo va en una mano, como cuando solo hay 1 objeto.
isaacg
@isaacg Supuse que 1 objeto no era válido, ya que claramente tenía que sostenerlo con una mano. ¿Realmente no sabría qué regresar para eso [[x], []]?
FryAmTheEggman
Supongo que sí, probablemente esté bien a menos que OP diga lo contrario.
isaacg
@isaacg He publicado una respuesta a continuación. Da la respuesta correcta para 1 elemento (tuve que agregar un byte más al código)
Renae Lider
6

CJam, 19 18 bytes

{S+m!{S/1fb:*}$W=}

Esta es una función anónima que saca una matriz de enteros de la pila y devuelve una matriz de enteros separados por un espacio.

Gracias a @ jimmy23013 por su ingenioso :*truco, que ahorró 1 byte.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

S+    e# Append a space to the array of integers.
m!    e# Push the array of all possible permutations.
{     e# Sort the array by the following:
  S/  e#   Split the array at the space.
  1fb e#   Add the integers in each chunk (using base 1 conversion).
  :*  e#   Push the product of both sums.
}$    e# Permutations with a higher product will come last.
W=    e# Select the last permutation.

Denotar el peso total de las bolsas de compras con W . Luego, si las bolsas en una de las manos pesan W / 2 - D / 2 , las de la otra mano deben pesar y W - (W / 2 - D / 2) = W / 2 + D / 2 .

Estamos tratando de minimizar la diferencia D . Pero (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , que se hace más grande a medida que D se hace más pequeño.

Por lo tanto, el producto máximo corresponde a la diferencia mínima.

Dennis
fuente
Creo que :*... W=debería funcionar.
jimmy23013
@ jimmy23013: ¡Gracias! Eso hizo que mi respuesta fuera mucho más interesante.
Dennis
5

Python 2.7, 161 , 160

código

from itertools import*
m=input();h=sum(m)/2.;d=h
for r in(c for o in range(len(m)+1) for c in combinations(m,o)):
 t=abs(h-sum(r))
 if t<=d:d=t;a=r
print a

Algoritmo

2 x W una mano = Peso total
W una mano ~ Peso total / 2

Verifique si cada combinación se acerca a la mitad del peso total. Iterar y encontrar el mejor.

entrada

>>>[1,2,3,4]

salida

(2, 3)

La tupla mostrada va en una mano, las que no se muestran van en la otra (no está en contra de las reglas).

Renae Lider
fuente
Puede guardar un byte haciendofrom itertools import*
DJMcMayhem
4

JavaScript ( ES6 ) 117

Usar una máscara de bits para probar cada división posible, por lo que se limita a 31 elementos (de acuerdo con las reglas). Al igual que la respuesta de referencia, genera solo una mano. Nota: busco la diferencia mínima> = 0 para evitar Math.abs, ya que para cada min <0 hay otro> 0, simplemente intercambiando manos.

Para probar: ejecute el fragmento en Firefox, ingrese una lista de números separados por comas o espacios.

f=(l,n)=>{ // the unused parameter n is inited to 'undefined'
  for(i=0;++i<1<<l.length;t<0|t>=n||(r=a,n=t))
    l.map(v=>(t+=i&m?(a.push(v),v):-v,m+=m),m=1,t=0,a=[]);
  alert(r)
}

// Test

// Redefine alert to avoid that annoying popup when testing
alert=x=>O.innerHTML+=x+'\n';

go=_=>{
  var list=I.value.match(/\d+/g).map(x=>+x); // get input and convert to numbers
  O.innerHTML += list+' -> ';
  f(list);
}
#I { width: 300px }
<input id=I value='7 7 7 10 11'><button onclick='go()'>-></button>

<pre id=O></pre>

edc65
fuente
2

Haskell, 73 bytes

import Data.List
f l=snd$minimum[(abs$sum l-2*sum s,s)|s<-subsequences l]

Emite una lista de elementos en una mano. Los elementos que faltan van a la otra parte.

Uso: f [7,7,7,10,11]->[7,7,7]

Para todas las subsecuencias sde la lista de entrada, lcalcule el valor absoluto de la diferencia de peso entre sy los elementos que faltan l. Encuentra el mínimo.

nimi
fuente
1

Haskell, 51 bytes

f l=snd$minimum$((,)=<<abs.sum)<$>mapM(\x->[x,-x])l

El formato de salida es que los pesos de la izquierda son positivos y los de la derecha son negativos.

>> f [2,1,5,4,7]
[-2,-1,5,4,-7]

Para generar cada división posible, usamos mapM(\x->[x,-x])lpara negar cada posible subconjunto de elementos. Luego, ((,)=<<abs.sum)etiqueta cada uno con su suma absoluta y snd$minimum$((,)=<<abs.sum)toma el elemento etiquetado más pequeño.

No pude obtenerlo sin puntos debido a problemas de verificación de tipo.

xnor
fuente
@WillNess Todos están en preludio en la versión actual.
xnor
Por cierto, el siguiente código libre de puntos funciona en el símbolo GHCi: snd.minimum.map((,)=<<abs.sum).mapM(\x->[x,-x]). Son 47 bytes. (aunque tengo una versión anterior instalada ...)
Will Ness
0

R (234)

Una solución más larga y lenta con R.

Función:

function(p){m=sum(p)/2;n=100;L=length(p);a=matrix(0,n,L+2);for(i in 1:n){idx=sample(1:L,L);a[i,1:L]=idx;j=1;while(sum(p[idx[1:j]])<=m){a[i,L+1]=abs(sum(p[idx[1:j]])-m);a[i,L+2]=j;j=j+1}};b=which.min(a[,L+1]);print(p[a[b,1:a[b,L+2]]])}


Entrada esperada - vector con los pesos.
Salida esperada: vector con los pesos para una mano.


Ejemplo

> Weight(c(1,2,3,4))
[1] 3 2
> Weight(c(10,1,2,3,4))
[1] 10
> Weight(c(40,20,80,50,100,33,2))
[1] 100  40  20  2
> Weight(c(7,7,7,10,11))
[1] 7 7 7

Versión de código legible para humanos:

weight <- function(input) {
  mid <- sum(input)/2
  n <- 100
  input_Length <- length(input)
  answers <- matrix(0, n, input_Length+2)
  for(i in 1:n){
    idx <- sample(1:input_Length, input_Length)
    answers[i, 1:input_Length ] <- idx
    j <- 1
    while(sum(input[idx[1:j]]) <= mid){
        answers[i, input_Length+1] <- abs(sum(input[idx[1:j]]) - mid)
        answers[i, input_Length+2] <- j
        j <- j + 1
    }
  }
  best_line <- which.min(answers[, input_Length+1])
  print(paste("weight diference: ", answers[best_line, input_Length+1]))
  print(input[answers[best_line, 1:answers[best_line, input_Length+2]]])
}
AndriusZ
fuente
0

Axioma, 292 bytes

R==>reduce;F(b,c)==>for i in 1..#b repeat c;p(a)==(#a=0=>[a];w:=a.1;s:=p delete(a,1);v:=copy s;F(s,s.i:=concat([w],s.i));concat(v,s));m(a)==(#a=0=>[[0],a];#a=1=>[a,a];b:=p(a);r:=[a.1];v:=R(+,a)quo 2;m:=abs(v-a.1);F(b,(b.i=[]=>1;d:=abs(v-R(+,b.i));d<m=>(m:=d;r:=copy b.i);m=0=>break));[[m],r])

Una aplicación de fuerza bruta. Esto minimizaría el conjunto

A={abs(reduce(+,a)quo 2-reduce(+,x))|x in powerSet(a)}

porque si es mínimo

y=min(A)=abs(reduce(+,a)quo 2-reduce(+,r))

sería mínimo también

2*y=abs(reduce(+,a)-2*reduce(+,r))=abs((reduce(+,a)-reduce(+,r))-reduce(+,r)) 

donde (reduce (+, a) -reduce (+, r)) y reduce (+, r) son el peso 2 de dos bolsas. (Pero esa última fórmula no me encuentra el mínimo, en la aplicación). Ungolf y resultados

-- Return the PowerSet or the Powerlist of a
powerSet(a)==
    #a=0=>[a]
    p:=a.1;s:=powerSet delete(a,1);v:=copy s
    for i in 1..#s repeat s.i:=concat([p],s.i)
    concat(v,s)

-- Return one [[m], r] where
-- r is one set or list with reduce(+,r)=min{abs(reduce(+,a)quo 2-reudece(+,x))|x in powerSet(a)}
-- and m=abs(reduce(+,a) quo 2-reduce(+,r))
-- because each of two part, has to have the same weight
MinDiff(a)==
    #a=0=>[[0],a]
    #a=1=>[ a ,a]
    b:=powerSet(a)
    r:=[a.1];v:=reduce(+,a) quo 2;m:=abs(v-a.1)
    for i in 1..#b repeat
        b.i=[]=>1
        k:=reduce(+,b.i)
        d:=abs(v-k)
        d<m=>(m:=d;r:=copy b.i)
        m=0=>break
    [[m],r]

--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

(5) -> a:=randList(12,1,10000)
   (5)  [8723,1014,2085,5498,2855,1121,9834,326,7416,6025,4852,7905]
                                                       Type: List Integer
(6) -> m(a)
   (6)  [[1],[1014,2085,5498,1121,326,6025,4852,7905]]
                                                  Type: List List Integer
(7) -> x:=reduce(+,m(a).2);[x,reduce(+,a)-x]
   (7)  [28826,28828]
                                               Type: List PositiveInteger
(8) -> m([1,2,3,4])
   (8)  [[0],[2,3]]
                                                  Type: List List Integer
(9) -> m([10,1,2,3,4])
   (9)  [[0],[10]]
                                                  Type: List List Integer
(10) -> m([40,20,80,50,100,33,2])
   (10)  [[0],[40,20,100,2]]
                                                  Type: List List Integer
(11) -> m([7,7,7,10,11])
   (11)  [[0],[10,11]]
                                                  Type: List List Integer
RosLuP
fuente