Oui. [http://d.hatena.ne.jp/shindannin/20111202/1322833089] (http://d.hatena.ne.jp/shindannin/20111202/1322833089) Que.
Problème 4 Problème de sac à dos 0-1 Il existe N types de marchandises (poids poids [i], valeur valeur [i], 0≤i <N). Les sacs à dos peuvent être emballés avec des articles jusqu'à un poids total de W. Vous ne pouvez sélectionner qu'un seul élément au maximum. Vous souhaitez emballer des articles dans un sac à dos afin que la valeur totale des articles à emballer soit maximisée. Quelle est la valeur maximale de la valeur totale à ce moment-là?
Conditions d'entrée / de contrainte
int N: N est un entier qui vérifie 1 ≤ N ≤ 20
int W: W est un entier qui vérifie 0 ≤ N ≤ 10000000
vector
Exemple 1 Entrée: N = 5, W = 10, poids = {1,2,3,4,3} valeur = {2,5,10,2,6} Sortie: 23 Emballant le 0e, le 1er, le 2e et le 4e, le poids est 1 + 2 + 4 + 3 = 10 et la valeur est 2 + 5 + 10 + 6 = 23, ce qui est le meilleur.
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)
Je me demande si c'est écrit comme ça lorsque je l'utilise pour d'autres problèmes.py
youso =Nombre d'éléments donnés(Nombre de couleurs et sac à dos)
seigen =Vous pouvez choisir jusqu'à 2 couleurs et un poids de 10 ou moins
max_value= -1
#Apparemment, la plage la plus externe(1<<Nombre d'éléments)C'est comme écrire.
for all in range(1<<youso):
#Définissez la valeur initiale du poids et de la valeur qui sort de chaque combinaison sur 0
sum_weight = 0
sum_value = 0
#Une petite boucle de numéro d'élément inconnu
for i in range(youso):
#Une autre méthode de vérification des bits. Il semble. .. ..
#Bit est debout(1)Si vous décidez que vous l'utilisez, vous n'êtes pas debout(0)Si tel est le cas, je me demande s'il est jugé non utilisé. .. ..
if (all>>i & 1):
#Ajouter le poids et la valeur des éléments jugés en cours d'utilisation
sum_weight += weight[[i]
sum_value += value[i]
if sum_weight<=W:
#Première fois max_La valeur est-Puisqu'il est 1, somme_La valeur de valeur est attribuée.
#À partir de la deuxième fois, le plus grand nombre est max_Il semble être attribué à la valeur.
max_value = max(max_value,sum_value)
print max_value
Hmmm, je ne peux pas comprendre à moins que je l'utilise de plus en plus. ..
Postscript J'ai essayé de l'utiliser mais cela n'a pas fonctionné http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B
How many ways? Parmi les nombres de 1 à n, sélectionnez 3 nombres sans duplication et créez un programme pour trouver le nombre de combinaisons dont la somme est x.
Par exemple, une combinaison de 3 de 1 à 5 avec un total de 9
1 + 3 + 5 = 9 2 + 3 + 4 = 9 Il y a deux manières.
J'ai écrit pour
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
Quand j'ai essayé plusieurs modèles avant de les soumettre, les fans ont tourné violemment à partir de 20 à 20 environ et c'est devenu un terrible désastre. .. .. Je vous serais reconnaissant si vous pouviez trouver un guide pour résoudre ce problème ou lire ceci.
La soumission de réponse elle-même était pour triple. ..
pour triple.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