Twoim zadaniem jest zbudowanie algorytmu (programu lub funkcji), który może zoptymalizować pakowanie owoców z przenośnika taśmowego do worków, które zostaną wysłane do sprzedawców, optymalizując pod kątem największej liczby worków.

Każda torebka musi ważyć co najmniej pewną ilość, ale wszelkie nadwyżki tracą zysk, ponieważ tę wagę można wykorzystać do napełnienia innej torebki. Twoja maszyna pakująca zawsze ma przed oczyma nowoce z kolejki i może tylko dodać te nowoce do (pojedynczej) torby, która jest przetwarzana. Nie może patrzeć poza npierwsze elementy w kolejce. Program zawsze wie dokładnie, ile już ma w wadze.

Innym sposobem na zwizualizowanie tego jest posiadanie przenośnika taśmowego z obszarem ładunkowym nna końcu, z którego należy pobrać owoc, zanim pojawi się nowy owoc. Wszelkie resztki owoców i niepełną torbę na końcu są odrzucane.

Wejścia

• Lista / tablica wag owoców w kolejce (dodatnie liczby całkowite)
• Minimalna masa całkowita worków (dodatnia liczba całkowita)
• Lookahead n(dodatnia liczba całkowita)

Wydajność

Twój algorytm powinien zwracać dla wszystkich toreb masy owoców w nich, w dowolny sposób dogodny dla Ciebie i Twojego języka, niezależnie od tego, czy jest to wartość standardowa, czy wartość zwrotna, czy coś innego. Powinieneś być w stanie uruchomić program i obliczyć swój wynik w ciągu minuty na komputerze.

Przykład

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]

Punktacja

Twój algorytm zostanie przetestowany w sześciu seriach na partii 10000 pomarańczy, którą dla ciebie przygotowałem, na wyprzedzeniach od 2 do 7, w tym na obu końcach. Zapakujesz je w torby o wadze co najmniej 1000 sztuk. Pomarańcze są zwykle rozmieszczone ze średnią masą 170 i standardowym odchyleniem 13, jeśli to jest pomocne.

Twój wynik będzie sumą liczby worków z sześciu serii. Najwyższy wynik wygrywa. Standardowe luki są niedozwolone.

Prosta przykładowa implementacja i płyta testowa pakietu testowego w Haskell

Worki Python 3, 9964 9981

Idea tego rozwiązania jest podobna do pomysłów Jonathana, JayCe i fortraan, ale z funkcją punktacji =)

To rozwiązanie łączy najlepsze podzbiory obszaru widokowego z widokiem na score.

score zapewnia zamówienie na podzestawy przy użyciu następującego schematu:

• Podzbiór uzupełniający torbę jest lepszy niż ten, który nie jest
• Jeden podzbiór uzupełniający torbę jest lepszy niż inny, jeśli ma mniejszą nadwagę
• Jeden podzbiór nieukończący torby jest lepszy niż inny, jeśli jego średnia jest bliższa oczekiwaniom w torbie

expected_mean próbuje przewidzieć, jak powinny wyglądać pozostałe wartości (zakładając, że ich wybór jest optymalny).

UPD :

Oto kolejna obserwacja: możesz włożyć dowolne pomarańcze z najlepszego podzbioru do torby bez szkody dla wydajności algorytmu. Przesunięcie dowolnej części nadal pozwala przenieść resztę później, a reszta powinna nadal być najlepszą opcją (bez nowych pomarańczy), jeśli punktacja jest prawidłowa. Ponadto w ten sposób istnieje szansa na dynamiczne ulepszenie zestawu kandydatów do włożenia do torby, widząc więcej pomarańczy przed napełnieniem torby. I chcesz wiedzieć jak najwięcej informacji, więc nie ma sensu przenosić do torby więcej niż jednej pomarańczy w danym momencie.

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)))

Spróbuj!

Worki Python 3 , 9796

Opierając się na odpowiedzi Jonathana:

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

Zależy to od zestawu zasilającego z książki kucharskiej itertool. Najpierw znajduje optymalny podzbiór bufora na podstawie minimalizacji różnicy od wagi docelowej dla wszystkich podzbiorów, a następnie wybiera element z tego podzbioru na podstawie tego samego kryterium. Jeśli żaden optymalny podzbiór nie wybierze z całego bufora.

C ++ 17, 9961,58 _{(średnia dla niektórych losowych nasion)}

(przewiń w dół, aby uzyskać wyjaśnienie, jeśli nie znasz 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';
}

// Ciekawostka: początkowo pisałem <o >tutaj i dziwnego
// dlaczego liczba worków jest nawet mniej niż
// Algorytm probabilistyczny

(jeśli <jest używany w zasadzie, algorytm próbuje zminimalizować liczbę worków)

Zainspirowany tą odpowiedzią .

Łącze TIO na 250 powtórzeń: Wypróbuj online!

Definiuje funkcję (właściwie wygląda jak funkcja, jest to struktura), pick_orangektóra, biorąc pod vector<int> weightsuwagę wagę pomarańczy i int remainpozostałą wagę torby, zwraca indeks pomarańczy, którą należy wybrać.

Algorytm:

powtarzanie 500razy {
generuje losowe (fałszywe) pomarańcze (rozkład normalny ze średnią 170 i stddev 13), aż pojawią się N_NEW_ORANGES=7pomarańcze
wybierają dowolny podzbiór, którego suma jest najmniejsza i nie mniejsza niż remain(funkcja to backtrackrobi)
oznacza wszystkie pomarańcze w tym podzbiorze jako dobre
}

uśrednij, ile razy pomarańcze oznaczone jako dobre (prawdziwe) pomarańcze o równej wadze
zwracają najlepszą pomarańczę

W programie są 3 stałe zakodowane, których nie można wywnioskować z problemu:

• Losowe ziarno (to nie jest ważne)
• N_NEW_ORANGES(długość prognozy). Zwiększenie tego powoduje, że program działa wykładniczo dłużej (ponieważ cofanie się)
• liczba powtórzeń. Zwiększenie tego powoduje, że program działa liniowo dłużej.

Worki Python 2 , 9756

Rozwijajmy pomarańczę ...

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

Wypróbuj online!

Zawsze zbiera owoce z bufora, co minimalizuje bezwzględną różnicę nowej masy i masy docelowej.

Worki Python 3, 9806

Opierając się na odpowiedziach Jonathana i 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

Wypróbuj online!

Jak to działa

Powiedz, że w torbie znajduje się 900 jednostek i dostępne są 2 owoce: 99 jednostek owoców i 101 jednostek owoców. Jeśli owoc 99 jednostek znajduje się bliżej początku listy oczekujących, minwybierze go zamiast 101. Jeśli tak się stanie, będziemy potrzebować kolejnego owocu, aby wypełnić pozostałą potrzebną 1 jednostkę. W tych przypadkach zmieniłem program, aby faworyzować owoce o wyższej wartości.

Robi to, sortując, a następnie odwracając listę oczekujących przed ustawieniem zasilania.

PHP, 9975 worków

• Jeśli to możliwe, idź po 5 pomarańczy
• Przy uruchamianiu torby wybierz ekstremalną wartość, później zrównoważ
• Jeśli to możliwe, natychmiast napełnij torbę
• Staraj się utrzymywać wagę torby blisko szacowanej krzywej (n * 200 dla 5 toreb, n * 167 dla 6 toreb itp.)

najdłuższy ze wszystkich zgłoszeń, ale powinien być czytelny

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 Razem: 9975

Spróbuj

Python 3, 9855 9928 9947 9956 9964 Worki

Oparty na kodzie startowym Jonathana Allana, ale nieprzygotowany do bycia czytelnym.

Pomysł: Ponieważ 1000/170 = 5,88, staramy się wybierać owoce zbliżone do 1000/6 (bawiłem się magicznymi stałymi). Jeśli jednak ostatni owoc w torbie może zminimalizować straty, używamy tego zamiast tego.

To rozwiązanie ma docelowe wartości sumy dla każdego dodanego owocu. Prawdopodobnie się tu zatrzymam. Użyłem Nelder-Mead, aby znaleźć moją targetstablicę:

[  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 worków

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))

Program worków 9947 jest szczególnie prosty:

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

Rubin , 9967 worków

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

Wypróbuj online!

Jeśli masz wystarczająco dużo masy, aby wypełnić torbę, znajdź najlżejszy podzbiór, który może wypełnić torbę, i użyj najlżejszej pomarańczy z tego podzbioru. W przeciwnym razie uzyskaj pozostałą wagę możliwie najbliżej wielokrotności 170.

Rakieta / Schemat, 9880 worków

Aby zdecydować, który kawałek owocu dodać do torby, porównaj optymalną wagę torby z wagą torby z dodatkowym kawałkiem owoców. Jeśli jest to optymalna waga, użyj jej. Jeśli ma nadwagę, zminimalizuj nadwyżkę. Jeśli ma niedowagę, zminimalizuj nadwyżkę po próbie pozostawienia optymalnej luki.

;; 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 worków

To była moja pierwsza próba:

• łapczywie napełnił torbę partią, kiedy mógł,
• lub spłukał wszystkie pomarańcze do torby, gdy nie mógł.

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]

Wypróbuj online!

Haskell , 9981 worków

The Angs → Jonathan Allan → JayCe → fortraan → Alex → Roman Czyborra python Cegła golfowa mogłaby jeździć z powrotem do Haskell, aby uzyskać pewną matematyczną czystość wzdłuż tego samego głównego nurtu myślenia

• tylko jedna pomarańcza zostaje zwolniona przed dodaniem nowej pomarańczy
• uprzedzenie preferuje wystarczające owoce ((<miss)==False<True )
• stronniczość preferuje owoce zbliżone do najbardziej prawdopodobnej liczby całkowitej

• w tym całkowitą odwrotnej
  (m-n)/sqrt(n)==(n+1-m)/sqrt(n+1) <==> n=sqrt(m^2-1/4)-1/2 od A https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables

  

przyprawiony niepotrzebnymi bezsensownościami

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]

Wypróbuj online!

bez uzyskiwania innego wzrostu liczbowego na zebranych 9981 sieci pomarańczy, podczas gdy mój pakujący torby 10k011 chwytający niezdrowe pomarańcze z powrotem z niezamkniętych worków został zdyskwalifikowany przez user69850 w osobie user202729 → Jo King → ovs, dlatego zasłużona nagroda trafiła do Alexa