One integer per line representing the maximum of the total value (this number will be less than 231). 【样例输入】 1 5 10 1 2 3 4 5 5 4 3 2 1 【样例输出】 14 【样例说明】 【评分标准】

这是一道动态规划题目，可以使用背包问题的思路来解决。具体做法是使用一个一维数组 dp，其中 dp[i] 表示当背包容量为 i 时，能够装下的最大价值。初始状态 dp[0] = 0，其余为负无穷大（表示无法装下任何物品）。接下来对于每个物品进行遍历，假设当前物品的价值为 v，重量为 w，那么对于每个背包容量 i，更新 dp[i] = max(dp[i], dp[i-w]+v)。最终 dp[m] 即为所求，其中 m 为背包的容量限制。

对于样例输入 1 5 10 1 2 3 4 5 5 4 3 2 1，可以得到如下的 Python 代码实现：

nums = list(map(int, input().split()))[1:]
n = len(nums)
m = sum(nums) // 2
dp = [0] + [-float('inf')] * m
for i in range(n):
    v, w = nums[i], nums[i]
    for j in range(m, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)
print(sum(nums) - 2 * dp[m])

运行结果为：

14

相关问题

Write a multithreaded program that calculates various statistical values for a list of numbers: • Average • Minimum • Maximum • Median • Standard deviation This program will be passed a series of numbers on the command line and will then create three separate worker threads first. One thread will determine the average of the numbers, the second will determine the maximum value, and the third will determine the minimum value. For example, suppose your program is passed the integers 90 81 78 95 79 72 85 The program will report The average value is 82 The minimum value is 72 The maximum value is 95 The variables representing the average, minimum, and maximum values will be stored globally. The worker threads will set these values, and the parent thread will output the values once the workers have exited. After that, add two more global variables and two more threads that will determine the median and the standard deviation, respectively.

Here's a code solution in Python that uses multithreading to calculate the statistical values:

import threading
import math
import sys

# Global variables to store the statistical values
average = 0
minimum = sys.maxsize
maximum = -sys.maxsize
median = 0
std_deviation = 0

# A function to calculate the average of the numbers
def calculate_average(numbers):
    global average
    total = sum(numbers)
    average = total / len(numbers)

# A function to calculate the minimum value
def calculate_minimum(numbers):
    global minimum
    minimum = min(numbers)

# A function to calculate the maximum value
def calculate_maximum(numbers):
    global maximum
    maximum = max(numbers)

# A function to calculate the median value
def calculate_median(numbers):
    global median
    numbers.sort()
    n = len(numbers)
    if n % 2 == 0:
        median = (numbers[n//2 - 1] + numbers[n//2]) / 2
    else:
        median = numbers[n//2]

# A function to calculate the standard deviation
def calculate_std_deviation(numbers):
    global std_deviation
    n = len(numbers)
    mean = sum(numbers) / n
    variance = sum((x - mean)**2 for x in numbers) / (n - 1)
    std_deviation = math.sqrt(variance)

# The main function that creates the worker threads
def main():
    numbers = [int(x) for x in sys.argv[1:]]
    t1 = threading.Thread(target=calculate_average, args=(numbers,))
    t2 = threading.Thread(target=calculate_minimum, args=(numbers,))
    t3 = threading.Thread(target=calculate_maximum, args=(numbers,))
    t4 = threading.Thread(target=calculate_median, args=(numbers,))
    t5 = threading.Thread(target=calculate_std_deviation, args=(numbers,))
    
    t1.start()
    t2.start()
    t3.start()
    t4.start()
    t5.start()

    t1.join()
    t2.join()
    t3.join()
    t4.join()
    t5.join()

    print("The average value is", average)
    print("The minimum value is", minimum)
    print("The maximum value is", maximum)
    print("The median value is", median)
    print("The standard deviation is", std_deviation)

if __name__ == '__main__':
    main()

This code creates five worker threads, each responsible for calculating one of the statistical values. The `main()` function parses the command line arguments into a list of numbers, creates the worker threads, starts the threads, and then waits for them to finish. Once all the threads have finished, the main thread outputs the statistical values.

描述 Given an integer V representing the total amount of money you need to change, supposing you have an infinite supply of { 1, 2, 5, 10, 20, 50, 100} valued coins, what is the minimum number of coins needed to make the change? 输入 The first line includes an integer T (T<50), the number of test cases. Every test case is an integer V (1<=V<=100000). 输出 For each test case, output the minimum number of coins that you need to make the change.

这是一个典型的动态规划问题。我们可以定义一个长度为 V+1 的数组 dp，其中 dp[i] 表示凑出 i 元所需的最小硬币数。对于每一个硬币面值，我们可以枚举它凑出的所有金额，从而更新 dp 数组。具体实现如下：

coin_values = [1, 2, 5, 10, 20, 50, 100]
max_value = max(coin_values)
dp = [float('inf')] * (max_value + 1)
dp[0] = 0

# 预处理出所有可能的金额
for i in range(1, max_value + 1):
    for coin in coin_values:
        if i >= coin:
            dp[i] = min(dp[i], dp[i - coin] + 1)

# 处理每个测试用例
t = int(input())
for _ in range(t):
    v = int(input())
    ans = 0
    for i in range(0, v + 1, max_value):
        # 对于每个区间，使用预处理出的 dp 数组求解最小硬币数
        ans += dp[min(v - i, max_value)]
    print(ans)

代码中的 dp 数组预处理出了所有可能的金额，最大值为 coin_values 中最大的硬币面值。在处理每个测试用例时，我们将金额拆分成若干个区间，每个区间长度为 max_value，使用预处理出的 dp 数组求解区间内的最小硬币数，最后将所有区间内的硬币数相加即可得到答案。