Ja. [http://d.hatena.ne.jp/shindannin/20111202/1322833089] (http://d.hatena.ne.jp/shindannin/20111202/1322833089) Als.
Problem 4 0-1 Rucksackproblem Es gibt N Arten von Waren (Gewichtsgewicht [i], Wertwert [i], 0 ≤ i <N). Rucksäcke können mit Gegenständen bis zu einem Gesamtgewicht von W verpackt werden. Sie können maximal ein Element auswählen. Sie möchten Artikel in einen Rucksack packen, damit der Gesamtwert der zu verpackenden Artikel maximiert wird. Was ist der Maximalwert des Gesamtwerts zu diesem Zeitpunkt?
Eingabe- / Einschränkungsbedingungen
int N: N ist eine ganze Zahl, die 1 ≤ N ≤ 20 erfüllt
int W: W ist eine ganze Zahl, die 0 ≤ N ≤ 10000000 erfüllt
Vektor
Beispiel 1 Eingabe: N = 5, W = 10, Gewicht = {1,2,3,4,3} Wert = {2,5,10,2,6} Ausgabe: 23 Beim Packen des 0., 1., 2. und 4. ist das Gewicht 1 + 2 + 4 + 3 = 10 und der Wert 2 + 5 + 10 + 6 = 23, was das Beste ist.
a.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import sys
import io
import re
import math
N = 5
W = 10
weight = [1,2,3,4,3]
value = [2,5,10,2,6]
max_value = -1
for all_count in range(1<<N):
sum_weight = 0
sum_value = 0
for i in range(N):
if (all_count >> i & 1):
sum_weight += weight[i]
sum_value += value[i]
if sum_weight <= W:
max_value = max(max_value,sum_value)
print (max_value)
Ich frage mich, ob es so geschrieben ist, wenn es für andere Probleme verwendet wird.py
youso =Anzahl der angegebenen Elemente(Anzahl der Farben und Rucksack)
seigen =Sie können bis zu 2 Farben wählen und 10 oder weniger wiegen
max_value= -1
#Anscheinend die äußerste Reichweite(1<<Elementanzahl)Es ist wie beim Schreiben.
for all in range(1<<youso):
#Setzen Sie den Anfangswert von Gewicht und Wert, der aus jeder Kombination hervorgeht, auf 0
sum_weight = 0
sum_value = 0
#Eine kleine unbekannte Elementnummernschleife
for i in range(youso):
#Eine andere Methode zur Bitprüfung. Es scheint. .. ..
#Bit steht(1)Wenn Sie sich entscheiden, dass Sie es verwenden, stehen Sie nicht(0)Wenn ja, frage ich mich, ob es als nicht verwendet beurteilt wird. .. ..
if (all>>i & 1):
#Fügen Sie das Gewicht und den Wert der Elemente hinzu, deren Verwendung bestimmt ist
sum_weight += weight[[i]
sum_value += value[i]
if sum_weight<=W:
#Erstmal max_Wert ist-Da es 1 ist, Summe_Der Wert des Wertes wird zugewiesen.
#Ab dem zweiten Mal beträgt die größere Anzahl max_Es scheint dem Wert zugeordnet zu sein.
max_value = max(max_value,sum_value)
print max_value
Hmmm, ich kann es nicht verstehen, wenn ich das nicht immer mehr benutze. ..
Nachtrag Ich habe es versucht, aber es hat nicht funktioniert http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B
How many ways? Wählen Sie aus den Zahlen von 1 bis n 3 Zahlen ohne Duplizierung aus und erstellen Sie ein Programm, um die Anzahl der Kombinationen zu ermitteln, deren Summe x ist.
Zum Beispiel eine Kombination von 3 von 1 bis 5 mit insgesamt 9
1 + 3 + 5 = 9 2 + 3 + 4 = 9 Es gibt zwei Möglichkeiten.
Ich habe für geschrieben
a.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import time
import sys
import io
import re
import math
l = []
ans=0
(n,x)=map(int, raw_input().split())
for a in range(1,n+1):
l.append(a)
for sou in range(1<<n):
sum_weight=0
sum_value=0
for i in range(n):
if (sou >> i & 1):
sum_value+=l[i]
sum_weight+=1
if sum_value==x and sum_weight==3:
ans+=1
print ans
Als ich vor dem Einreichen mehrere Muster ausprobierte, drehten sich die Fans von ungefähr 20 bis 20 heftig um und es wurde eine schreckliche Katastrophe. .. .. Ich würde mich freuen, wenn Sie eine Anleitung finden könnten, wie Sie dies beheben oder lesen können.
Die Antwort selbst war dreifach. ..
für dreifach.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import timeit
import time
import sys
import io
import re
import math
#start = time.time()
#start = time.clock()
while True:
l = []
(n,x)=map(int, raw_input().split())
if n==x==0:
break
ans=0
for a in range(1,n+1):
l.append(a)
for i in l:
if i > 98: break
for j in l:
if j > 99 or i+j>x: break
p=0
for k in l:
p=i+j+k
if (i != j and j != k and k != i) and p==x and i<j<k:
ans+=1
print ans
Recommended Posts