Gegeben:

• Eine natürliche Zahl S .
• Eine Liste von N rationalen Gewichten W , die sich zu 1 summieren.

Geben Sie eine Liste L von N nicht negativen ganzen Zahlen zurück, so dass:

(1) sum(L) = S
(2) sum((S⋅W_i - L_i)^2) is minimal

Mit anderen Worten, approximieren Sie S⋅W_is mit ganzen Zahlen so genau wie möglich.

Beispiele:

1 [0.4 0.3 0.3] = [1 0 0]
3 [0 1 0] = [0 3 0]
4 [0.3 0.4 0.3] = [1 2 1]
5 [0.3 0.4 0.3] = [2 2 1] or [1 2 2] but not [1 3 1]
21 [0.3 0.2 0.5] = [6 4 11]
5 [0.1 0.2 0.3 0.4] = [1 1 1 2] or [0 1 2 2]
4 [0.11 0.3 0.59] = [1 1 2]
10 [0.47 0.47 0.06] = [5 5 0]
10 [0.43 0.43 0.14] = [4 4 2]
11 [0.43 0.43 0.14] = [5 5 1]

Regeln:

• Sie können ein beliebiges Eingabeformat verwenden oder nur eine Funktion bereitstellen, die die Eingabe als Argumente akzeptiert.

Hintergrund:

Dieses Problem tritt auf, wenn S verschiedener Arten von Gegenständen in verschiedenen Anteilen W _i in Bezug auf die Arten angezeigt wird.

Ein weiteres Beispiel für dieses Problem ist die proportionale politische Repräsentation, siehe das Aufteilungsparadoxon . Die letzten beiden Testfälle sind als Alabama-Paradox bekannt.

Als Statistiker erkannte ich dieses Problem als äquivalent zu einem Problem bei der Identifizierung von Stichprobengrößen bei der Durchführung einer geschichteten Stichprobe. In dieser Situation möchten wir den Anteil jeder Schicht in der Stichprobe gleich dem Anteil jeder Schicht in der Bevölkerung machen. - @tomi

APL, 21

{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}

Dies ist eine Übersetzung aus der 37-Byte-CJam-Antwort von aditsu .

Testen Sie es online .

Erläuterung

 {      ⍵-⍺}            ⍝ Right argument - left argument.
 {  1=⍋⍋⍵-⍺}            ⍝ Make one of the smallest number 1, others 0.
 {⍵+1=⍋⍋⍵-⍺}            ⍝ Add the result and the right argument together.
 {⍵+1=⍋⍋⍵-⍺}⍣⍺          ⍝ Repeat that S times. The result of each iteration is the new right argument.
                  ⊂⍵    ⍝ Return enclosed W, which is taken as one unit in APL.
               ⍺0×⊂⍵    ⍝ Return S*W and 0*W.
{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}   ⍝ Make S*W the left argument, 0*W the right argument in the first iteration.

Python 2, 95 83 132 125 143

Mein erster (und zweiter) (und dritter) Algorithmus hatte Probleme. Nach einem (weiteren!) Umschreiben und weiteren Tests ist hier (ich hoffe wirklich) eine korrekte und schnelle Lösung:

def a(b,h):
 g=h;c=[];d=[]
 for w in b:f=int(w*h);d+=[f];c+=[h*w-f];g-=f
 if g:
  for e in sorted(c)[-g:]:i=c.index(e);c[i]=2;d[i]+=1
 return d

Die Quelle vor dem Minifier sieht nun so aus:

# minified 143 bytes
def golfalloc(weights, num):
    # Tiny seq alloc for golfing
    gap = num;
    errors = [];
    counts = []
    for w in weights :
        count = int(w*num);
        counts += [count];
        errors += [num*w - count];
        gap -= count
    if gap:
        for e in sorted(errors)[-gap:] :
            i = errors.index(e);
            errors[i] = 2;
            counts[i] += 1
    return counts

Die Tests geben Folgendes zurück:

Pass                    Shape    N               Result Error                        AbsErrSum
ok            [0.4, 0.3, 0.3]    1            [1, 0, 0] -0.60,+0.30,+0.30                 1.20
ok                  [0, 1, 0]    3            [0, 3, 0] +0.00,+0.00,+0.00                 0.00
ok            [0.3, 0.4, 0.3]    4            [1, 2, 1] +0.20,-0.40,+0.20                 0.80
ok            [0.3, 0.4, 0.3]    5            [2, 2, 1] -0.50,+0.00,+0.50                 1.00
ok            [0.3, 0.2, 0.5]   21           [6, 4, 11] +0.30,+0.20,-0.50                 1.00
ok       [0.1, 0.2, 0.3, 0.4]    5         [1, 1, 1, 2] -0.50,+0.00,+0.50,+0.00           1.00
ok          [0.11, 0.3, 0.59]    4            [1, 1, 2] -0.56,+0.20,+0.36                 1.12
ok         [0.47, 0.47, 0.06]   10            [5, 5, 0] -0.30,-0.30,+0.60                 1.20
ok         [0.43, 0.43, 0.14]   10            [4, 4, 2] +0.30,+0.30,-0.60                 1.20
ok         [0.43, 0.43, 0.14]   11            [5, 5, 1] -0.27,-0.27,+0.54                 1.08

Dieser Algorithmus ähnelt anderen Antworten hier. Es ist O (1) für num, also hat es die gleiche Laufzeit für ganze Zahlen 10 und 1000000. Es ist theoretisch O (nlogn) für die Anzahl der Gewichte (aufgrund der Sortierung). Wenn dies allen anderen kniffligen Eingabefällen standhält, ersetzt es den folgenden Algorithmus in meiner Programmier-Toolbox.

Bitte verwenden Sie diesen Algorithmus nicht mit etwas, das nicht golfig ist. Ich habe Kompromisse bei der Geschwindigkeit gemacht, um die Quellgröße zu minimieren. Der folgende Code verwendet dieselbe Logik, ist jedoch viel schneller und nützlicher:

def seqalloc(anyweights, num):
    # Distribute integer num depending on weights.
    # weights may be non-negative integers, longs, or floats.
    totalbias = float(sum(anyweights))
    weights = [bias/totalbias for bias in anyweights]
    counts = [int(w*num) for w in weights]
    gap = num - sum(counts)
    if gap:
        errors = [num*w - q for w,q in zip(weights, counts)]
        ordered = sorted(range(len(errors)), key=errors.__getitem__)
        for i in ordered[-gap:]:
            counts[i] += 1
    return counts

Der Wert von num hat keinen wesentlichen Einfluss auf die Geschwindigkeit. Ich habe es mit Werten von 1 bis 10 ^ 19 getestet. Die Ausführungszeit variiert linear mit der Anzahl der Gewichte. Auf meinem Computer dauert es 0,15 Sekunden mit 10 ^ 5 Gewichten und 15 Sekunden mit 10 ^ 7 Gewichten. Beachten Sie, dass die Gewichte nicht auf Brüche beschränkt sind, die sich zu eins summieren. Die hier verwendete Sortiertechnik ist ebenfalls etwa doppelt so schnell wie der traditionelle sorted((v,i) for i,v in enumerate...)Stil.

Ursprünglicher Algorithmus

Dies war eine Funktion in meiner Toolbox, die ein wenig für Golf modifiziert wurde. Es war ursprünglich aus einer SO-Antwort . Und es ist falsch.

def seqalloc(seq, num):
    outseq = []
    totalw = float(sum(seq))
    for weight in seq:
        share = int(round(num * weight / totalw)) if weight else 0
        outseq.append(share)
        totalw -= weight
        num -= share
    return outseq

Es gibt eine Annäherung, ist aber nicht immer korrekt, obwohl die Summe (outseq) == num beibehalten wird. Schnell aber nicht zu empfehlen.

Vielen Dank an @alephalpha und @ user23013 für das Erkennen der Fehler.

BEARBEITEN: Setzen Sie totalw (d) auf 1, da OP angibt, dass die Summe der Gewichte immer 1 ist. Jetzt 83 Bytes.

EDIT2: Fehler behoben für [0.4, 0.3, 0.3], 1.

EDIT3: Abgebrochener fehlerhafter Algorithmus. Besser hinzugefügt.

EDIT4: Das wird lächerlich. Ersetzt durch den richtigen (ich hoffe es wirklich) Algorithmus.

EDIT5: Nicht-Golf-Code für andere hinzugefügt, die diesen Algorithmus möglicherweise verwenden möchten.

Mathematica, 67 50 46 45 Zeichen

f=(b=⌊1##⌋;b[[#~Ordering~-Tr@#&[b-##]]]++;b)&

Ungolfed:

f[s_, w_] := Module[{a = s*w, b, c, d},
  b = Floor[a];
  c = b - a;
  d = Ordering[c, -Total[c]];
  b[[d]] += 1;
  b]

Beispiel:

f[5,{0.1,0.2,0.3,0.4}]

{1, 1, 1, 2}

CJam - 37

q~:W,0a*\:S{[_SWf*]z::-_:e<#_2$=)t}*p

Probieren Sie es online aus

Erläuterung:

q~             read and evaluate the input
               (pushing the number and the array on the stack)
:W,            save the array in variable W and calculate its length (N)
0a*            make an array of N zeros (the initial "L")
\:S            swap it with the number and save the number in S
{…}*           execute the block S times
    [_SWf*]    make a matrix with 2 rows: "L" and S*W
    z          transpose the matrix, obtaining rows of [L_i S*W_i]
    ::-_       convert to array of L_i-S*W_i and duplicate
    :e<        get the smallest element
    #          find its index in the unsorted array,
               i.e. the "i" with the largest S*W_i-L_i
    _2$=)t     increment L_i
p              print the result nicely

Anmerkungen:

• Die Komplexität liegt bei O (S * N), daher wird es für große S sehr langsam
• CJam fehlen schmerzlich arithmetische Operatoren für 2 Arrays, was ich später implementieren möchte

Andere Idee - 46

q~:Sf*_:m[_:+S\-@[1f%_,,]z{0=W*}$<{1=_2$=)t}/p

Probieren Sie es online aus

Dies ist viel einfacher und effizienter, aber leider viel länger. Die Idee hier ist, mit L_i = Etage (S * W_i) zu beginnen, die Differenz (sagen wir D) zwischen S und ihrer Summe zu bestimmen, die D-Indizes mit dem größten Bruchteil von S * W_i zu finden (durch Sortieren und Nehmen von oben D) und inkrementiere L_i für diese Indizes. Komplexität O (N * log (N)).

JavaScript (ES6) 126 130 104 115 156 162 194

Nach all den Kommentaren und Testfällen in @ CarpetPythons Antwort zurück zu meinem ersten Algorithmus. Leider funktioniert die intelligente Lösung nicht. Die Implementierung wurde etwas verkürzt, es werden immer noch alle möglichen Lösungen ausprobiert, der quadratische Abstand berechnet und das Minimum eingehalten.

Bearbeiten Für jedes Ausgabeelement mit dem Gewicht w sind 'alle' möglichen Werte nur 2: trunc (w * s) und trunc (w * s) +1, daher gibt es nur (2 ** elemensts) mögliche Lösungen zum Ausprobieren.

Q=(s,w)=>
  (n=>{
    for(i=0;
        r=q=s,(y=i++)<1<<w.length;
        q|r>n||(n=r,o=t))
      t=w.map(w=>(f=w*s,q-=d=0|f+(y&1),y/=2,f-=d,r+=f*f,d));
  })()||o

Test In Firefox / Firebug - Konsole

;[[ 1,  [0.4, 0.3, 0.3]      ]
, [ 3,  [0, 1, 0]            ]
, [ 4,  [0.3, 0.4, 0.3]      ]
, [ 5,  [0.3, 0.4, 0.3]      ]
, [ 21, [0.3, 0.2, 0.5]      ]
, [ 5,  [0.1, 0.2, 0.3, 0.4] ]
, [ 4,  [0.11, 0.3, 0.59]    ]
, [ 10, [0.47, 0.47, 0.06]   ]
, [ 10, [0.43, 0.43, 0.14]   ]
, [ 11, [0.43, 0.43, 0.14]   ]]
.forEach(v=>console.log(v[0],v[1],Q(v[0],v[1])))

Ausgabe

1 [0.4, 0.3, 0.3] [1, 0, 0]
3 [0, 1, 0] [0, 3, 0]
4 [0.3, 0.4, 0.3] [1, 2, 1]
5 [0.3, 0.4, 0.3] [1, 2, 2]
21 [0.3, 0.2, 0.5] [6, 4, 11]
5 [0.1, 0.2, 0.3, 0.4] [0, 1, 2, 2]
4 [0.11, 0.3, 0.59] [1, 1, 2]
10 [0.47, 0.47, 0.06] [5, 5, 0]
10 [0.43, 0.43, 0.14] [4, 4, 2]
11 [0.43, 0.43, 0.14] [5, 5, 1]

Das ist eine intelligentere Lösung. Single Pass auf Weigth Array.
Für jeden Durchgang finde ich den aktuellen Maximalwert in w. Ich ändere diesen Wert an Ort und Stelle mit dem gewichteten ganzzahligen Wert (aufgerundet). Wenn also s == 21 und w = 0,4 sind, erhalten wir 0,5 * 21 -> 10,5 -> 11. Ich speichere diesen Wert negiert, daher kann er nicht in der nächsten Schleife als max gefunden werden. Dann reduziere ich die Gesamtsumme entsprechend (s = s-11) und reduziere auch die Gesamtsumme der Gewichte in der Variablen f.
Die Schleife endet, wenn kein Maximum über 0 gefunden werden kann (alle Werte! = 0 wurden verwaltet).
Zuletzt gebe ich die Werte wieder auf positiv zurück. Warnung Dieser Code ändert das vorhandene Gewichtungsarray, sodass es mit einer Kopie des ursprünglichen Arrays aufgerufen werden muss

F=(s,w)=>
 (f=>{
  for(;j=w.indexOf(z=Math.max(...w)),z>0;f-=z)
    s+=w[j]=-Math.ceil(z*s/f);
 })(1)||w.map(x=>0-x)

Mein erster Versuch

Nicht so eine kluge Lösung. Für jedes mögliche Ergebnis wird der Unterschied ausgewertet und das Minimum beibehalten.

F=(s,w,t=w.map(_=>0),n=NaN)=>
  (p=>{
    for(;p<w.length;)
      ++t[p]>s?t[p++]=0
      :t.map(b=>r+=b,r=p=0)&&r-s||
        t.map((b,i)=>r+=(z=s*w[i]-b)*z)&&r>n||(n=r,o=[...t])
  })(0)||o

Ungolfed und erklärt

F=(s, w) =>
{
  var t=w.map(_ => 0), // 0 filled array, same size as w
      n=NaN, // initial minumum NaN, as "NaN > value"  is false for any value
      p, r
  // For loop enumerating from [1,0,0,...0] to [s,s,s...s]
  for(p=0; p<w.length;)
  {
    ++t[p]; // increment current cell
    if (t[p] > s)
    {
      // overflow, restart at 0 and point to next cell
      t[p] = 0;
      ++p;
    }
    else
    {
      // increment ok, current cell is the firts one
      p = 0;
      r = 0;
      t.map(b => r += b) // evaluate the cells sum (must be s)
      if (r==s)
      {
        // if sum of cells is s
        // evaluate the total squared distance (always offset by s, that does not matter)
        t.map((b,i) => r += (z=s*w[i]-b)*z) 
        if (!(r > n))
        {
          // if less than current mininum, keep this result
          n=r
          o=[...t] // copy of t goes in o
        }
      }
    }
  }
  return o
}

CJam, 48 Bytes

Eine einfache Lösung für das Problem.

q~:Sf*:L,S),a*{m*{(+}%}*{1bS=},{L]z::-Yf#:+}$0=p

Eingabe geht wie

[0.3 0.4 0.3] 4

Erläuterung:

q~:S                                 "Read and parse the input, store sum in S";
    f*:L                             "Do S.W, store the dot product in L";
         S),                         "Get array of 0 to S";
        ,   a*                       "Create an array with N copies of the above array";
              {m*{(+}%}*             "Get all possible N length combinations of 0 to S ints";
                        {1bS=},      "Filter to get only those which sum up to S";
{L]z::-Yf#:+}$                       "Sort them based on (S.W_i - L_i)^2 value";
 L                                   "Put the dot product after the sum combination";
  ]z                                 "Wrap in an array and transpose";
    ::-                              "For each row, get difference, i.e. S.W_i - L_i";
       Yf#                           "Square every element";
          :+                         "Take sum";
              0=p                    "After sorting on sum((S.W_i - L_i)^2), take the";
                                     "first element, i.e. smallest sum and print it";

Probieren Sie es hier online aus

Pyth: 40 Bytes

Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUH

Dies definiert eine Funktion gmit 2 Parametern. Sie können es so nennen Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4.

Probieren Sie es online aus: Pyth Compiler / Executor

Erläuterung:

mms+*G@Hb}bklHyUH     (G is S, H is the list of weights)
m             yUH    map each subset k of [0, 1, ..., len(H)-1] to:
 m          lH          map each element b of [0, 1, ..., len(H)-1] to: 
    *G@Hb                  G*H[b]
   +     }bk               + b in k
  s                       floor(_)

Dies schafft alle möglichen Lösungen L, wo L[i] = floor(S*W[i])oder L[i] = floor(S*W[i]+1). Zum Beispiel wird die Eingabe 4 [0.3 0.4 0.3erstellt [[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]].

fqsTG...  
f    ... only use the solutions, where
 qsTG       sum(solution) == G

Nur [[2, 1, 1], [1, 2, 1], [1, 1, 2]]bleiben.

Mhosm^-*Ghded2C,HN
  o                  order the solutions by
   s                   the sum of 
    m         C,HN       map each element d of zip(H, solution) to
     ^-*Ghded2           (G*d[0] - d[1])^2
 h                   use the first element (minimum)
M                    define a function g(G,H): return _

Mathematica 108

s_~f~w_:=Sort[{Tr[(s*w-#)^2],#}&/@ 
Flatten[Permutations/@IntegerPartitions[s,{Length@w},0~Range~s],1]][[1,2]]

f[3, {0, 1, 0}]
f[4, {0.3, 0.4, 0.3}]
f[5, {0.3, 0.4, 0.3}]
f[21, {0.3, 0.2, 0.5}]
f[5, {0.1, 0.2, 0.3, 0.4}]

{0, 3, 0}
{1, 2, 1}
{1, 2, 2}
{6, 4, 11}
{0, 1, 2, 2}

Erläuterung

Ungolfed

f[s_,w_]:=
Module[{partitions},
partitions=Flatten[Permutations/@IntegerPartitions[s,{Length[w]},Range[0,s]],1];
Sort[{Tr[(s *w-#)^2],#}&/@partitions][[1,2]]]

IntegerPartitions[s,{Length@w},0~Range~s]Gibt alle ganzzahligen Partitionen von zurück s, wobei Elemente aus der Menge verwendet werden, {0, 1, 2, ...s}mit der Einschränkung, dass die Ausgabe die gleiche Anzahl von Elementen wie in der Menge der Gewichte enthalten soll w.

Permutations gibt alle geordneten Anordnungen jeder ganzzahligen Partition an.

{Tr[(s *w-#)^2],#}Gibt {error, permutation} für jede Permutation eine Liste der geordneten Paare zurück .

Sort[...] sortiert die Liste von {{error1, permutation1},{error2, permutation2}...according to the size of the error.

[[1,2]]]oder Part[<list>,{1,2}]gibt das zweite Element des ersten Elements in der sortierten Liste von zurück {{error, permutation}...}. Mit anderen Worten, es wird die Permutation mit dem kleinsten Fehler zurückgegeben.

R, 85 80 76

Verwendet die Hare Quota-Methode.

Ein Paar wurde entfernt, nachdem die Spezifikation angezeigt wurde, dass W 1 ergibt

function(a,b){s=floor(d<-b*a);s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s}

Testlauf

> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(3,c(0,1,0))
[1] 0 3 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(1,c(0.4,0.3,0.3))
[1] 1 0 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(4,c(0.3, 0.4, 0.3))
[1] 1 2 1
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.3, 0.4, 0.3))
[1] 1 2 2
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(21,c(0.3, 0.2, 0.5))
[1]  6  4 11
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.1,0.2,0.3,0.4))
[1] 1 1 1 2
>

Python, 139 128 117 Bytes

def f(S,W):
 L=(S+1,0,[]),
 for n in W:L=[(x-i,y+(S*n-i)**2,z+[i])for x,y,z in L for i in range(x)]
 return min(L)[2]

Vorherige itertools-Lösung, 139 Bytes

from itertools import*
f=lambda S,W:min((sum(x)!=S,sum((S*a-b)**2for a,b in zip(W,x)),list(x))for x in product(*tee(range(S+1),len(W))))[2]

Octave, 87 76

Golf:

function r=w(s,w)r=0*w;for(i=1:s)[m,x]=max(s*w-r);r(x)+=1;endfor endfunction

Ungolfed:

function r=w(s,w)
  r=0*w;   # will be the output
  for(i=1:s)
    [m,x]=max(s*w-r);
    r(x)+=1;
  endfor
endfunction

("Endfor" und "Endfunction"! Ich werde nie gewinnen, aber ich spiele gerne Golf mit einer "echten" Sprache.)

T-SQL, 167 265

Weil ich diese Herausforderungen auch gerne in einer Abfrage versuche.

Verwandelte es in eine Inline-Funktion, um die Spezifikation besser anzupassen, und erstellte einen Typ für die Tabellendaten. Es kostete ein bisschen, aber das würde niemals ein Anwärter sein. Jede Anweisung muss separat ausgeführt werden.

CREATE TYPE T AS TABLE(A INT IDENTITY, W NUMERIC(9,8))
CREATE FUNCTION W(@ int,@T T READONLY)RETURNS TABLE RETURN SELECT CASE WHEN i<=@-SUM(g)OVER(ORDER BY(SELECT\))THEN g+1 ELSE g END R,A FROM(SELECT A,ROW_NUMBER()OVER(ORDER BY (W*@)%1 DESC)i,FLOOR(W*@)g FROM @T)a

In Benutzung

DECLARE @ INT = 21
DECLARE @T T
INSERT INTO @T(W)VALUES(0.3),(0.2),(0.5)
SELECT R FROM dbo.W(@,@T) ORDER BY A

R
---------------------------------------
6
4
11