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
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