[PYTHON] 4th night of loop with for

Yes. [http://d.hatena.ne.jp/shindannin/20111202/1322833089] (http://d.hatena.ne.jp/shindannin/20111202/1322833089) Than.

Problem 4 0-1 knapsack problem There are N types of goods (weight weight [i], value value [i], 0≤i <N). Knapsacks can be packed with items up to a total weight of W. You can only select one item at a maximum. You want to pack items in a knapsack so that the total value of the items to be packed is maximized. What is the maximum value of the total value at that time?

Input / constraints

int N: N is an integer that satisfies 1 ≤ N ≤ 20 int W: W is an integer that satisfies 0 ≤ N ≤ 10000000 vector weight: weight has N elements. An integer that satisfies 1 ≤ weight [i] ≤ 10000000 vector value: value has N elements, an integer that satisfies 1 ≤ value [i] ≤ 10000000

Example 1 Input: N = 5, W = 10, weight = {1,2,3,4,3} value = {2,5,10,2,6} Output: 23 Packing the 0th, 1st, 2nd, and 4th, the weight is 1 + 2 + 4 + 3 = 10, and the value is 2 + 5 + 10 + 6 = 23, which is the best.

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)

I wonder if this is how to write it when using it for other problems.py



youso =Number of elements given(Number of colors and knapsack)
seigen =You can choose up to 2 colors and weight 10 or less

max_value= -1
#Apparently the outermost range(1<<Element count)It's like writing in.
for all in range(1<<youso):
#Set the initial value of weight and value that comes out of each combination to 0
    sum_weight = 0
    sum_value = 0

#A little unknown element number loop
    for i in range(youso):
#Another method of bit checking. It seems. .. ..
#Bit is standing(1)If you decide that you are using it, you are not standing(0)If so, I wonder if it is judged not to be used. .. ..
        if (all>>i & 1):
#Add the weight and value of the element determined to be in use
            sum_weight += weight[[i]
            sum_value += value[i]
    if sum_weight<=W:
#First time max_value is-Since it is 1, sum_The value of value is assigned.
#From the second time onward, the larger number is max_It seems to be assigned to value.
        max_value = max(max_value,sum_value)
print max_value

Hmmm, I can't understand unless I use this more and more. ..

Postscript I tried using it but it didn't work http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B

How many ways? From the numbers from 1 to n, select 3 numbers without duplication and create a program to find the number of combinations whose sum is x.

For example, a combination of 3 from 1 to 5 with a total of 9

1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are two ways.

I wrote for

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 

When I tried several patterns before submitting, the fans turned fiercely from around 20 20 and it became a terrible disaster. .. .. I would appreciate it if you could find a guide such as fixing this or reading this.

The answer submission itself was for triple. ..

for 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

4th night of loop with for
The third night of the loop with for
The second night of the loop with for
Algorithm learned with Python 8th: Evaluation of algorithm
Algorithm learned with Python 13th: Tower of Hanoi
Add the attribute of the object of the class with the for statement
Summary of tools for operating Windows GUI with Python
[For beginners] Quantify the similarity of sentences with TF-IDF
Precautions when operating with string for TmeStampType of PySpark
[For beginners] Summary of standard input in Python (with explanation)
Simulation of late damages for child support delinquency with python
Turn an array of strings with a for statement (Python3)
Let's play with 4D 4th
Equation of motion with sympy
Loop video loading with opencv
Parallel processing with Parallel of scikit-learn
Percentage of LIKE for pymysql
Overview of Docker (for beginners)
Prediction of Nikkei 225 with Pytorch 2
Memories of fighting with Selenium
Prediction of Nikkei 225 with Pytorch
Implementation of Scale-space for SIFT
Be careful of LANG for UnicodeEncodeError when printing Japanese with Python 3
I searched for a similar card of Hearthstone with Deep Learning
I made a lot of files for RDP connection with Python
Introduction of library PyPhi for dealing with integrated information theory (IIT)
Output log file with Job (Notebook) of Cloud Pak for Data
[Let's play with Python] Aiming for automatic sentence generation ~ Completion of automatic sentence generation ~
Check the memory protection of linux kerne with the code for ARM
Output csv with different number of digits for each column with numpy