Su misión es construir un algoritmo (programa o función) que pueda optimizar el empaque de la fruta de una cinta transportadora en bolsas para enviarlas a los minoristas, optimizando la mayor cantidad de bolsas.

Cada bolsa tiene que pesar al menos una cierta cantidad, pero cualquier exceso se pierde, ya que ese peso podría usarse para llenar otra bolsa. Su máquina de ensacado siempre tiene una anticipación de nfrutas de la cola y solo puede elegir agregar cualquiera de estas nfrutas a la (única) bolsa que se está procesando. No puede mirar más allá de los nprimeros elementos en la cola. El programa siempre sabe exactamente cuánto peso hay en la bolsa.

Otra forma de visualizar esto es tener una cinta transportadora con un área de carga de tamaño nal final, desde donde se debe tomar una fruta antes de que llegue una nueva fruta. Cualquier fruta sobrante y una bolsa no llena al final se descartan.

Entradas

• Lista / matriz de pesos de frutas en cola (enteros positivos)
• Peso total mínimo para bolsas (entero positivo)
• Lookahead n(entero positivo)

Salida

Su algoritmo debe devolver para todas las bolsas el peso de las frutas en ellas, por cualquier medio que sea conveniente para usted y su idioma, ya sea un estándar o un valor de retorno u otra cosa. Debería poder ejecutar el programa y calcular su puntaje en un minuto en su computadora.

Ejemplo

Total weight 1000, lookahead of 3 and fruit queue: 
[171,163,172,196,156,175,162,176,155,182,189,142,161,160,152,162,174,172,191,185]

One possible output (indented to show how the lookahead affects the bagging):
[171,163,172,    156,175,    176]
                        [162,    155,182,189,    161,160]
                                                        [152,162,174,172,191,185]

Tanteo

Su algoritmo se probará en seis ejecuciones en un lote de 10000 naranjas que he preparado para usted, en lookaheads que van de 2 a 7, inclusive en ambos extremos. Deberá empacarlos en bolsas de al menos 1000 unidades. Las naranjas se distribuyen normalmente con un peso medio de 170 y una desviación estándar de 13, si eso es de alguna ayuda.

Su puntaje será la suma de la cantidad de bolsas de las seis carreras. El puntaje más alto gana. Las lagunas estándar no están permitidas.

Implementación de ejemplo simple y paquete de pruebas en Haskell

Python 3, 9964 9981 bolsas

La idea de esta solución es similar a las de Jonathan, JayCe y fortraan, pero con una función de puntuación =)

Esta solución agrega los mejores subconjuntos del área de búsqueda anticipada según el score.

score proporciona un orden sobre los subconjuntos utilizando el siguiente esquema:

• Un subconjunto que completa una bolsa es mejor que uno que no
• Un subconjunto que completa una bolsa es mejor que otro si tiene menos exceso de peso
• Un subconjunto que no completa una bolsa es mejor que otro si su media está más cerca de lo que se espera que esté en una bolsa

expected_mean intenta predecir cómo debería verse el resto de los valores (suponiendo que su elección sea óptima).

UPD :

Aquí hay otra observación: puede colocar las naranjas del mejor subconjunto en la bolsa sin dañar el rendimiento del algoritmo. Mover cualquier parte de él todavía permite mover el resto después, y el resto aún debería ser la mejor opción (sin nuevas naranjas) si la puntuación es correcta. Además, de esta manera, existe la posibilidad de mejorar dinámicamente el conjunto de candidatos para poner en la bolsa al ver más naranjas antes de llenar la bolsa. Y desea saber tanta información como sea posible, por lo que no tiene sentido mover más de una naranja a la bolsa en un momento dado.

import itertools as it
import math
from functools import partial
from collections import Counter


mean, std = 170, 13


def powerset(list_, max_items):
    return it.chain.from_iterable(it.combinations(list_, r) for r in range(1, max_items + 1))


def expected_mean(w):
    spread = std * 1
    return max(mean - spread, min(mean + spread, w / max(1, round(w / mean))))


def score(weight_needed, candidate):
    c_sum = sum(candidate)
    c_mean = c_sum / len(candidate)
    if c_sum >= weight_needed:
        return int(-2e9) + c_sum - weight_needed
    return abs(expected_mean(weight_needed) - c_mean)


def f(oranges, min_bag_weight, lookahead):
    check = Counter(oranges)

    oranges = oranges.copy()
    result = []
    bag = []

    while oranges:
        weight_needed = min_bag_weight - sum(bag)

        lookahead_area = oranges[:lookahead]
        tail = oranges[lookahead:]

        to_add = min(powerset(lookahead_area, lookahead),
                     key=partial(score, weight_needed))
        to_add = min(powerset(to_add, 1),
                     key=partial(score, weight_needed))

        bag.extend(to_add)
        for x in to_add:
            lookahead_area.remove(x)
        oranges = lookahead_area + tail

        if sum(bag) >= min_bag_weight:
            result.append(bag)
            bag = []

    assert check == Counter(oranges) + Counter(bag) + sum(map(Counter, result), Counter())

    return result


if __name__ == '__main__':
    with open('oranges') as file:
        oranges = list(map(int, file))
    res = [f(oranges, 1000, l) for l in range(2, 7+1)]
    print(sum(map(len, res)))

¡Intentalo!

Python 3 , 9796 bolsas

Sobre la base de la respuesta de Jonathan:

import itertools as it

def powerset(iterable):
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

def f(a,m,l):
 r=[];b=[]
 while a:
  c =  min(list(powerset(a[:l])),key=lambda w: abs(sum(b)+sum(w)-m))
  if sum(c)==0:
   c = a[:l]
  b+=[a.pop(a.index(min(c,key=lambda w: abs(sum(b)+w-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

Esto se basa en powerset del libro de cocina de itertool. Primero encuentra el subconjunto óptimo del búfer basándose en minimizar la diferencia del peso objetivo para todos los subconjuntos, y luego selecciona un elemento de este subconjunto según el mismo criterio. Si no se selecciona un subconjunto óptimo de todo el búfer.

C ++ 17, 9961.58 _{(promedio sobre algunas semillas aleatorias)}

(Desplácese hacia abajo para obtener una explicación si no conoce C ++)

#include<iostream>

#include<vector>
#include<random>

std::mt19937 engine(279); // random engine
// random distribution of the oranges
std::normal_distribution dist (170.,13.);

int constexpr N_NEW_ORANGES=7;

/** Input format: Current remaining weight of the bag (remain) and 
the weight of the oranges (weights)
Output: the index of the orange to be pick.
*/
struct pick_orange{
    std::vector<int>weights,sum_postfix;int remain;

    /// returns {min excess, mask}, (index) is the LSB
    std::pair<int,int> backtrack(int index, int remain) {
        if(sum_postfix[index]<remain)return {1e9,0};
        int min_excess=1e9, good_mask=0;
        for(int next=index;next<N_NEW_ORANGES;++next){
            if(weights[next]==remain){
                return {0, 1<<(next-index)};
            }else if(weights[next]>remain){
                if(weights[next]-remain<min_excess){
                    min_excess=weights[next]-remain;
                    good_mask=1<<(next-index);
                }
            }else{
                auto[excess,mask]=backtrack(next+1,remain-weights[next]);
                if(excess<min_excess){
                    min_excess=excess;
                    good_mask=(mask<<1|1)<<(next-index);
                }
            }
        }
        return {min_excess,good_mask};
    } 

    int ans;

    pick_orange(std::vector<int> weights_,int remain_)
        :weights(std::move(weights_)),remain(remain_){

        int old_size=weights.size();

        std::vector<int> count (N_NEW_ORANGES, 0);
        weights.resize(N_NEW_ORANGES, 0);

        sum_postfix.resize(N_NEW_ORANGES+1);
        sum_postfix.back()=0;

        for(int _=0; _<500; ++_){

            for(int i=old_size;i<N_NEW_ORANGES;++i)
                weights[i] = dist(engine);

            // prepare sum postfix
            for(int i=N_NEW_ORANGES;i-->0;)
                sum_postfix[i]=weights[i]+sum_postfix[i+1];

            // auto[excess,mask]=backtrack(0,remain);
            int mask = backtrack(0,remain).second;

            for(int i=0; 

                mask
                // i < N_NEW_ORANGES

                ; mask>>=1, ++i){

                // if(mask&1)std::cout<<'(';
                // std::cout<<weights[i];
                // if(mask&1)std::cout<<')';
                // std::cout<<' ';

                count[i]+=mask&1;
            }

            // std::cout<<"| "<<remain<<" | "<<excess<<'\n';

        }

        std::vector<double> count_balanced(old_size, -1);
        for(int i=0;i<old_size;++i){
            if(count_balanced[i]>-1)continue;
            int sum=0,amount=0;
            for(int j=i;j<old_size;++j)
                if(weights[j]==weights[i]){sum+=count[j];++amount;}

            double avg=sum;avg/=amount;
            for(int j=i;j<old_size;++j)
                if(weights[j]==weights[i])count_balanced[j]=avg;
        }

        ans=old_size-1;
        for(int i=ans;i-->0;)
            if(count_balanced[i]>count_balanced[ans])ans=i;
        // Fun fact: originally I wrote `<` for `>` here and wonder
        // why the number of bags is even less than that of the
        // randomized algorithm
    }

    operator int()const{return ans;}
};


#include<iostream>
#include<fstream>
#include<algorithm>

int main(){
    // read input from the file "data"
    std::ifstream data ("data");
    std::vector<int> weights;
    int weight;while(data>>weight)weights.push_back(weight);

    int constexpr BAG_SIZE=1000;
    int total_n_bag=0;
    for(int lookahead=2;lookahead<=7;++lookahead){
        auto weights1=weights;
        std::reverse(weights1.begin(),weights1.end());

        int remain=BAG_SIZE,n_bag=0;
        std::vector<int> w;
        for(int _=lookahead;_--;){
            w.push_back(weights1.back());
            weights1.pop_back();
        }
        while(!weights1.empty()){
            int index=pick_orange(w,remain);

            remain-=w[index];
            if(remain<=0){
                ++n_bag;remain=BAG_SIZE;

                if(n_bag%100==0)
                    std::cout<<n_bag<<" bags so far..."<<std::endl;
            }
            w[index]=weights1.back();weights1.pop_back();
        }

        while(!w.empty()){
            int index=pick_orange(w,remain);
            remain-=w[index];
            if(remain<=0){++n_bag;remain=BAG_SIZE;}
            w.erase(w.begin()+index);
        }

        std::cout<<"lookahead = "<<lookahead<<", "
            "n_bag = "<<n_bag<<'\n';
        total_n_bag += n_bag;
    }

    std::cout<<"total_n_bag = "<<total_n_bag<<'\n';
}

// Dato curioso: originalmente escribió <para >aquí y maravilla
// qué el número de bolsas es incluso menor que la de la
// algoritmo aleatorio

(si <se usa básicamente, el algoritmo intenta minimizar el número de bolsas)

Inspirado por esta respuesta .

Enlace TIO para 250 repeticiones: ¡ Pruébelo en línea!

Define una función (en realidad solo se ve como una función, es una estructura) pick_orangeque, dado vector<int> weightsel peso de las naranjas y int remainel peso restante de la bolsa, devuelve el índice de la naranja que debe seleccionarse.

Algoritmo:

repetir 500tiempos {
genera naranjas aleatorias (falsas) (distribución normal con media 170 y stddev 13) hasta que haya N_NEW_ORANGES=7naranjas,
elija cualquier subconjunto cuya suma sea menor y no menor que remain(la función lo backtrackhace)
marca todas las naranjas en ese subconjunto como buenas
}

promediar el número de veces que las naranjas que se marcan como buenas de las naranjas (reales) con el mismo peso
devuelven la mejor naranja

Hay 3 constantes codificadas en el programa que no pueden deducirse del problema:

• La semilla aleatoria (esto no es importante)
• N_NEW_ORANGES(la duración de la predicción). Aumentar esto hace que el programa se ejecute exponencialmente más largo (porque retrocede)
• Número de repeticiones. Al aumentar esto, el programa se ejecuta linealmente más tiempo.

Python 2 , 9756 bolsas

Hagamos rodar la naranja ...

def f(a,m,l):
 r=[];b=[]
 while a:
  b+=[a.pop(a.index(min(a[:l],key=lambda w:abs(sum(b)+w-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

Pruébalo en línea!

Siempre recoge la fruta del tampón, lo que minimiza la diferencia absoluta del nuevo peso y el peso objetivo.

Python 3, 9806 bolsas

Sobre la base de las respuestas de Jonathan y JayCe:

import itertools as it

def powerset(iterable):
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

def f(a,m,l):
 r=[];b=[]
 while a:
  c =  min(list(powerset(list(reversed(sorted(a[:l]))))),key=lambda w: abs((sum(b)+sum(w))-m))
  if sum(c)==0:
   c = a[:l]
  b+=[a.pop(a.index(min(c,key=lambda w: abs((sum(b)+w)-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

Pruébalo en línea!

Cómo funciona

Digamos que la bolsa tiene 900 unidades, y hay 2 frutas disponibles: una fruta de 99 unidades y una fruta de 101 unidades. Si la fruta de 99 unidades está más cerca del comienzo de la lista anticipada, entonces la minseleccionará en lugar de 101. Si esto sucede, ahora necesitaríamos otra fruta para completar la 1 unidad restante necesaria. Cambié el programa para favorecer la fruta de mayor valor en estos casos.

Para ello, ordena y luego invierte la lista anticipada antes de la configuración de potencia.

PHP, 9975 bolsas

• Si es posible, elige 5 naranjas
• Al comenzar la bolsa, elija un valor extremo, equilibre más tarde
• Si es posible, llene la bolsa inmediatamente
• Intente mantener el peso de la bolsa cerca de la curva estimada (n * 200 para 5 bolsas, n * 167 para 6 bolsas, etc.)

el más largo de todos los envíos pero debe ser legible

class Belt
{
    private $file;
    private $windowSize;
    private $buffer = [];

    public function __construct($filename, $windowSize) {
        $this->file = new \SplFileObject($filename);
        $this->windowSize = $windowSize;
        $this->loadBuffer();
    }

    public function reset($windowSize) {
        $this->file->seek(0);
        $this->windowSize = $windowSize;
        $this->buffer = [];
        $this->loadBuffer();
    }

    public function peekBuffer() {
        return $this->buffer;
    }

    public function pick($index) {
        if (!array_key_exists($index, $this->buffer)) {
            return null;
        }
        $value = $this->buffer[$index];
        unset($this->buffer[$index]);
        $this->buffer = \array_values($this->buffer);
        $this->loadBuffer();
        return $value;
    }

    private function loadBuffer() {
        for ($c = count($this->buffer); $c < $this->windowSize; $c++) {
            if ($this->file->eof()) {
                return;
            }
            $line = $this->file->fgets();
            if (false !== $line && "" !== $line) {
                $this->buffer[] = trim($line);
            }
        }
    }
}

class Packer
{

    const BAG_TARGET_WEIGHT = 1000;
    const MEAN_WEIGHT = 170;
    const MEAN_COUNT = 6; //ceil(self::BAG_WEIGHT/self::MEAN_WEIGHT);
    const MEAN_TARGET_WEIGHT = 167; //ceil(self::BAG_WEIGHT/self::MEAN_COUNT);

    public static function pack(Belt $belt, Picker $picker) {
        $bag = ["oranges" => [], "buffers" => []];
        $bags = [];
        while ($oranges = $belt->peekBuffer()) {

            $index = $picker->pick($oranges, \array_sum($bag["oranges"]));
            $orange = $belt->pick($index);
            $bag["oranges"][] = $orange;
            $bag["buffers"][] = $oranges;

            if (\array_sum($bag["oranges"]) >= self::BAG_TARGET_WEIGHT) {
                $bags[] = $bag;
                $bag = ["oranges" => [], "buffers" => []];
            }
        }
        return $bags;
    }
}

class Base
{
    public static function bestPermutation($elements, $weight = 0) {
        if (\array_sum($elements) < Packer::BAG_TARGET_WEIGHT - $weight) {
            return null;
        }
        $permute = function ($weight, $elements) use (&$permute) {
            if ($weight >= Packer::BAG_TARGET_WEIGHT) {
                return [];
            }
            $best = \PHP_INT_MAX;
            $bestElements = [];
            foreach ($elements as $key => $value) {
                $sum = $weight + $value;
                $els = [$value];
                if ($sum < Packer::BAG_TARGET_WEIGHT) {
                    $subSet = $elements;
                    unset($subSet[$key]);
                    $els = $permute($weight + $value, $subSet);
                    $els[] = $value;
                    $sum = $weight + \array_sum($els);
                }
                if ($sum >= Packer::BAG_TARGET_WEIGHT && $sum < $best) {
                    $best = $sum;
                    $bestElements = $els;
                }
            }
            return $bestElements;
        };
        $best = $permute($weight, $elements);

        return $best;
    }

    public function pickLightestOutOfHeavierThan($buffer, $targetWeight) {
        $b = -1;
        $bW = PHP_INT_MAX;
        foreach ($buffer as $key => $value) {
            if ($targetWeight <= $value && $value < $bW) {
                $b = $key;
                $bW = $value;
            }
        }
        return $b;
    }

    public function pickClosestTo($buffer, $targetWeight) {
        $b = -1;
        $bW = PHP_INT_MAX;
        foreach ($buffer as $key => $value) {
            $diff = \abs($targetWeight - $value);
            if ($diff < $bW) {
                $b = $key;
                $bW = $diff;
            }
        }
        return $b;
    }

    public function pickFurthestFrom($buffer, $targetWeight) {
        $b = -1;
        $bW = \PHP_INT_MIN;
        foreach ($buffer as $key => $value) {
            $diff = \abs($targetWeight - $value);
            if ($diff > $bW) {
                $b = $key;
                $bW = $diff;
            }
        }
        return $b;
    }

    public function findMax($buffer) {
        $i = -1;
        $m = 0;
        foreach ($buffer as $k => $v) {
            if ($v > $m) {
                $m = $v;
                $i = $k;
            }
        }
        return $i;
    }

    public function findMin($buffer) {
        $i = -1;
        $m = \PHP_INT_MAX;
        foreach ($buffer as $k => $v) {
            if ($v < $m) {
                $m = $v;
                $i = $k;
            }
        }
        return $i;
    }

    public function minimalOrangeCount($buffer, $weight) {
        $elementsToAdd = ceil((Packer::BAG_TARGET_WEIGHT - $weight) / Packer::MEAN_WEIGHT);
        $buffer = \array_merge($buffer,
            \array_fill(0, \floor($elementsToAdd / 2), Packer::MEAN_WEIGHT - 7),
            \array_fill(0, \floor($elementsToAdd / 2), Packer::MEAN_WEIGHT + 7),
            \array_fill(0, $elementsToAdd - \floor($elementsToAdd / 2) * 2, Packer::MEAN_WEIGHT)
        );
        \rsort($buffer);
        $orangeCount = 0;
        foreach ($buffer as $w) {
            $weight += $w;
            $orangeCount++;
            if ($weight >= Packer::BAG_TARGET_WEIGHT) {
                return $orangeCount;
            }
        }
        return $orangeCount + (Packer::BAG_TARGET_WEIGHT - $weight) / Packer::MEAN_WEIGHT;
    }
}


class Picker extends Base
{
    public function pick($buffer, $weight) {
        $weightNeeded = Packer::BAG_TARGET_WEIGHT - $weight;

        $minimalOrangeCount = $this->minimalOrangeCount($buffer, $weight);
        $orangeTargetWeight = ceil($weightNeeded / $minimalOrangeCount);

        if (0 === $weight) {
            $mean = \array_sum($buffer) / count($buffer);
            if ($mean > $orangeTargetWeight) {
                return $this->findMin($buffer);
            } elseif ($mean < $orangeTargetWeight) {
                return $this->findMax($buffer);
            }
            return $this->pickFurthestFrom($buffer, $orangeTargetWeight);
        }

        $i = $this->pickLightestOutOfHeavierThan($buffer, $weightNeeded);
        if (-1 !== $i) {
            return $i;
        }
        $i = $this->pickClosestTo($buffer, $orangeTargetWeight);
        return -1 !== $i ? $i : 0;
    }
}

$bagCount = 0;
$belt = new Belt(__DIR__ . "/oranges.txt", 0);
for ($l = 2; $l <= 7; $l++) {
    $belt->reset($l);
    $bags = Packer::pack($belt, new Picker());
    $bagCount += count($bags);
    printf("%d -> %d\n", $l, count($bags));
}
echo "Total: $bagCount\n";

2 -> 1645 3 -> 1657 4 -> 1663 5 -> 1667 6 -> 1671 7 -> 1672 Total: 9975

Intentalo

Python 3, 9855 9928 9947 9956 9964 bolsas

Basado en el código de inicio de Jonathan Allan, pero sin golf para ser legible.

Idea: desde 1000/170 = 5.88, tratamos de seleccionar frutas cercanas a 1000/6 (jugueteé con las constantes mágicas). Sin embargo, si la última fruta en la bolsa puede minimizar el desperdicio, la usamos en su lugar.

Esta solución tiene objetivos de suma de bolsas para cada fruta agregada. Probablemente me detendré aquí. Usé Nelder-Mead para encontrar mi targetsmatriz:

[  165.79534144   343.58443287   522.58081597   680.76516204   845.93431713 1063.17204861]

def f(a, m, l, targets):
    bags = []
    bag = []
    bag_sum = 0
    while a:
        buffer = a[:l]
        finishers = tuple(filter(lambda w: bag_sum + w >= m, buffer))
        if finishers:
            next_fruits = [min(finishers)]

        else:
            ind = len(bag)
            next_fruits = [min(buffer, key=lambda w: abs(targets[ind]-bag_sum-w))]

        for next_fruit in next_fruits:
            bag.append(a.pop(a.index(next_fruit)))
            bag_sum += bag[-1]

        if sum(bag) >= m:
            bags.append(bag)
            bag = []  # Reset bag
            bag_sum = 0

    return bags

9956 bolsos

from itertools import combinations

def f(a,m,l):
    bags = []
    bag = []
    while a:
        buffer = a[:l]
        next_fruit = None
        single_fruit = True

        finishers = [w for w in buffer if sum(bag) + w >= m ]
        if finishers: next_fruit = min(finishers)

        if not next_fruit:
            if len(buffer) >= 4 and sum(bag) < 600:
                next_fruits = min(combinations(buffer, 2), key=
                                  lambda ws: abs(2*169-sum(ws)))
                for fruit in next_fruits:
                    bag.append(a.pop(a.index(fruit)))

                single_fruit = False  # Skip adding single fruit

            else:
                next_fruit = min(buffer, key=lambda w: abs(171.5-w))

        if single_fruit:
            bag.append(a.pop(a.index(next_fruit)))

        if sum(bag)>=m:
            bags.append(bag)
            bag = []

    return bags


oranges = [int(x.strip()) for x in open("fruit.txt").readlines()]
bagLists = []
for lookahead in (2,3,4,5,6,7):
    bagLists.append(f(oranges[:], 1000, lookahead))


totalBagsOver1000 = sum(map(len, bagLists))
print('bags: ', (totalBagsOver1000))

El programa de bolsas 9947 es particularmente simple:

def f(a,m,l):
    bags = []
    bag = []
    while a:
        buffer = a[:l]
        next_fruit = None

        finishers = [w for w in buffer if sum(bag) + w >= m ]
        if finishers: next_fruit = min(finishers)

        if not next_fruit:
            next_fruit = min(buffer, key=lambda w: abs(171.5-w))

        bag.append(a.pop(a.index(next_fruit)))

        if sum(bag)>=m:
            bags.append(bag)
            bag = []

    return bags

Rubí , 9967 bolsas

def pick a, n
  if a.sum < n
    #return a.max
    d = n % 170
    return a.min_by{|w|
      [(w - d).abs, (w - d - 170).abs].min
    }
  end
  
  subsets = (0..a.length).map do |i|
    a.combination(i).to_a
  end.flatten(1)
  
  subsets.select!{|s|s.sum >= n}
  least_overkill = subsets.min_by{|s|s.sum}
  #puts "best: #{least_overkill.sort}"
  return least_overkill.min
end

def run list, weight, n
  bags = 0
  in_bag = 0
  while list.size > 0
    x = pick(list[0...n], weight - in_bag)
    i = list.index(x)
    raise new Exeption("not a valid weight") if(!i || i >= n)
    list.delete_at i
    in_bag += x
    if in_bag >= weight
      #puts in_bag
      in_bag = 0
      bags += 1
    end
  end
  return bags
end

Pruébalo en línea!

Si tiene suficiente peso para llenar la bolsa, encuentre el subconjunto más ligero que pueda llenar la bolsa y use la naranja más clara de ese subconjunto. De lo contrario, coloque el peso restante lo más cerca posible de un múltiplo de 170.

Raqueta / Esquema, 9880 bolsas

Para decidir qué fruta agregar a la bolsa, compare el peso óptimo de la bolsa con el peso de la bolsa con la fruta adicional. Si es el peso óptimo, úsalo. Si tiene sobrepeso, minimice la cantidad en exceso. Si tiene bajo peso, minimice la cantidad en exceso después de intentar dejar un espacio óptimo.

;; types

(define-struct bagger (fruit look tray bag bags)) ; fruit bagger

;; constants

(define MBW 1000) ; minimum bag weight
(define AFW 170) ; average piece-of-fruit weight
(define GAP (- MBW AFW)) ; targeted gap
(define FRUIT (file->list "fruit-supply.txt")) ; supplied fruit

;; utility functions

(define (weigh-it ls)
  (if (empty? ls)
      0
      (+ (car ls) (weigh-it (cdr ls)))))

(define (ref-to-car ls ref)
  (if (zero? ref)
      ls
      (let ((elem (list-ref ls ref)))
        (cons elem (remove elem ls)))))

;; predicates

(define (bag-empty? bgr) (empty? (bagger-bag bgr)))
(define (bag-full? bgr) (>= (weigh-it (bagger-bag bgr)) MBW))
(define (fruit-empty? bgr) (empty? (bagger-fruit bgr)))
(define (tray-empty? bgr) (empty? (bagger-tray bgr)))
(define (tray-full? bgr) (= (length (bagger-tray bgr)) (bagger-look bgr)))
(define (target-not-set? target value) (and (empty? target) (empty? value)))

;; pick best piece of fruit

(define (pf-rec tray bag i target value diff)
  (if (or (target-not-set? target value) (< diff value))
      (pick-fruit (cdr tray) bag (add1 i) i diff)
      (pick-fruit (cdr tray) bag (add1 i) target value)))

(define (pick-fruit tray bag i target value)
  (if (empty? tray)
      target
      (let ((weight (weigh-it (cons (car tray) bag))))
        (cond
          ((= weight MBW) i)
          ((> weight MBW) (pf-rec tray bag i target value (- weight MBW)))
          ((< weight MBW)
           (if (> weight GAP)
               (pf-rec tray bag i target value (- weight GAP))
               (pf-rec tray bag i target value (modulo (- MBW weight) AFW))))))))

;; load tray, bag, bags, etc.

(define (load-bag bgr)
  (let* ((tray (bagger-tray bgr))
         (bag (bagger-bag bgr))
         (weight (+ (weigh-it tray) (weigh-it bag))))
    (if (= weight MBW)
        (struct-copy bagger bgr
                     (tray empty)
                     (bag (append tray bag)))
        (let ((new-tray (ref-to-car tray (pick-fruit tray bag 0 empty empty))))
          (struct-copy bagger bgr
                       (tray (cdr new-tray))
                       (bag (cons (car new-tray) bag)))))))

(define (load-bags bgr)
  (struct-copy bagger bgr
               (bag empty)
               (bags (cons (bagger-bag bgr) (bagger-bags bgr)))))

(define (load-tray bgr)
  (struct-copy bagger bgr
               (fruit (cdr (bagger-fruit bgr)))
               (tray (cons (car (bagger-fruit bgr)) (bagger-tray bgr)))))

;; run the bagger factory

(define (run-bagger-aux bgr)
  (cond
    ((bag-full? bgr) (run-bagger-aux (load-bags bgr)))
    ((bag-empty? bgr)
     (cond
       ((tray-full? bgr) (run-bagger-aux (load-bag bgr)))
       ((tray-empty? bgr)
        (if (fruit-empty? bgr)
            (length (bagger-bags bgr))
            (run-bagger-aux (load-tray bgr))))
       (else
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bag bgr))
            (run-bagger-aux (load-tray bgr))))))
    (else
     (cond
       ((tray-full? bgr) (run-bagger-aux (load-bag bgr)))
       ((tray-empty? bgr)
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bags bgr))
            (run-bagger-aux (load-tray bgr))))
       (else
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bag bgr))
            (run-bagger-aux (load-tray bgr))))))))

(define (run-bagger fruit look)
  (run-bagger-aux (make-bagger fruit look empty empty empty)))

;; stackexchange problem run

(define (run-problem fruit looks)
  (if (empty? looks)
      0
      (+ (run-bagger fruit (car looks)) (run-problem fruit (cdr looks)))))

(run-problem FRUIT '(2 3 4 5 6 7)) ; result = 9880

Haskell , 9777 bolsos

Este fue mi primer intento:

• llenaba con avidez una bolsa con un lote cuando podía,
• o arrojó todas las naranjas a la bolsa cuando no pudo.

options[]=[(0,([],[]))]
options(first:rest)=[option|(sum,(now,later))<-options rest,
 option<-[(sum+first,(first:now,later)),(sum,(now,first:later))]]
bags _[_]_=[]
bags(w_sum,w_bag)(w_kilo:w_iyts)w_view=
 let(w_take,w_remd)=splitAt(w_view)w_iyts;
     w_fill=filter((>=(w_kilo-w_sum)).fst)(options w_take)
 in if null w_fill then bags(w_sum+sum w_take,w_bag++w_take)(w_kilo:w_remd)w_view
    else let(_,(w_now,w_later))=minimum w_fill in
         (w_bag++w_now):bags(0,[])(w_kilo:w_later++w_remd)w_view
main=print.sum$map(length.bags(0,[])(1000:batch))[2..7]

Pruébalo en línea!

Haskell , 9981 bolsas

The Angs → Jonathan Allan → JayCe → fortraan → Alex → La pitón codegolf Roman Czyborra podría ciclar de regreso a Haskell para obtener una mayor pureza matemática a lo largo del mismo tren de pensamiento principal

• solo una naranja se despide antes de agregar una nueva naranja en consideración
• el sesgo prefiere frutos suficientes ( (<miss)==False<True)
• el sesgo prefiere frutas cercanas al relleno entero más probable

• para ese entero invierta el
  (m-n)/sqrt(n)==(n+1-m)/sqrt(n+1) <==> n=sqrt(m^2-1/4)-1/2 de un https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables

  

sazonado con algunas inútiles innecesarias

subsets[]=[[]];subsets(f:t)=[r|s<-subsets t,r<-[s,f:s]]
mean=uncurry(div).(id***max 1).(sum&&&length)
bags[]_ _=[];bags batch(miss:have)n=let
 goal=div miss$ceiling(sqrt((fromIntegral miss/170)^2+1/4)-1/2)
 best=minimumBy.comparing.(((<miss)&&&(abs.(goal-))).); desk=take n batch
 pick=best id.best(if sum desk<miss then mean else sum).filter(>[]).subsets$desk
 in if pick < miss then bags(delete pick batch)(miss-pick:pick:have)n
       else (pick:have):bags(delete pick batch)[miss+sum have]n
main=print$id&&&sum$map(length.bags batch[1000])[2..7]

Pruébalo en línea!

sin producir un aumento numérico diferente en la cima de las 9981 redes de naranjas cosechadas antes, mientras que mi empacador de bolsas 10k011 que agarraba naranjas no aptas fuera de las bolsas no cerradas fue descalificado por el usuario 69850 en persona user202729 → Jo King → ovs, por lo tanto, la recompensa merecida fue para Alex