4ème nuit de boucle avec pour

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 poids: le poids comporte N éléments. Un entier qui satisfait 1 ≤ poids [i] ≤ 10000000 vector valeur: la valeur a N éléments, 1 ≤ valeur [i] ≤ 10000000

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

4ème nuit de boucle avec pour
La troisième nuit de la boucle avec pour
La deuxième nuit de la boucle avec pour
Ajouter des attributs d'objets de classe avec une instruction for
Récapitulatif des outils d'exploitation de l'interface graphique Windows avec Python
[Pour les débutants] Quantifier la similitude des phrases avec TF-IDF
Précautions lors du calcul avec une chaîne pour TmeStampType de PySpark
[Pour les débutants] Résumé de l'entrée standard en Python (avec explication)
Simulez des dommages-intérêts tardifs pour les frais de garde d'enfants en souffrance avec Python
Tourner un tableau de chaînes avec une instruction for (Python3)
Jouons avec la 4e dimension 4e
Equation de mouvement avec sympy
Chargement de la vidéo en boucle avec opencv
Traitement parallèle avec Parallel de scikit-learn
Pourcentage de LIKE pour pymysql
Vue d'ensemble de Docker (pour les débutants)
Prédiction de la moyenne Nikkei avec Pytorch 2
Souvenirs de combats avec Selenium
Prédiction de la moyenne Nikkei avec Pytorch
Implémentation de Scale-Space pour SIFT
Faites attention à LANG pour UnicodeEncodeError lors de l'impression du japonais avec Python 3
J'ai recherché une carte similaire de Hearthstone avec Deep Learning
J'ai créé beaucoup de fichiers pour la connexion RDP avec Python
Introduction de la bibliothèque PyPhi pour gérer la théorie de l'information intégrée (IIT)
Fichier journal de sortie avec Job (Notebook) de Cloud Pak for Data
[Jouons avec Python] Viser la génération automatique de phrases ~ Achèvement de la génération automatique de phrases ~
Vérifiez la protection de la mémoire de Linux Kerne avec le code pour ARM
Sortie csv avec un nombre différent de chiffres pour chaque colonne avec numpy