Blue Bridge Cup [12th provincial Championship] weight weighing Python 90 points

Typical knapsack problem , Use a one-dimensional list last_state To record the status , use 0 and 1 To show feasibility . Such as ：last_state[1] Indicates whether it can be added to the weight 1,last_state[4] Indicates whether it can be folded to the weight 4

First read the input , initialization last_state, And put last_state[0] Set to 1

num = int(input())
weight_list = list(map(int, input().split()))
length = sum(weight_list)
last_state = [0 for __ in range(length + 1)]
last_state[0] = 1

For example, the input weight is [1, 4, 6], We are thinking about [1], Think again [1, 4], Think again [1, 4, 6], That is to add the weights to the scope of consideration one by one

When making a state transition , First copy the state of the previous layer to this layer , namely new_state = last_state.copy(), And then based on last_state stay new_state Make modifications ( If you do not do so, a weight will be used many times , You can push it yourself )

stay last_state[sum] == 1 Under the circumstances , There are two cases of weight superposition (sum Is the total weight of the enumerated weights ,weight For the weight of the newly considered weight )：

• Forward stacking ：  Add a weight to get  new_state[sum + weight] = 1
• Reverse stack ： There are two cases

1. if weight = 4,sum = 1, Can be like 1 -> 0 -> 3 Stack like this ,new_state[weight - sum] = 1
2. if weight = 1,sum = 4, Can be like 4 -> 3 Stack like this ,new_state[sum - weight] = 1

for idx, weight in enumerate(weight_list):
new_state = last_state.copy()
# Inherit the state of the upper layer
for weight_sum in range(length + 1):
if last_state[weight_sum]:
# Before consideration n-1 When a weight , If... Can be reached weight_sum
temp = weight_sum + weight
if temp <= length:
new_state[temp] = 1
# Forward stacking
temp = weight_sum - weight
new_state[abs(temp)] = 1
# Reverse stack
last_state = new_state
print(sum(last_state[1:]))
# remove last_state[0], Sum is the answer 

90 The score is OK , end