商店里有n颗糖果,每一颗糖果的价格为b i ,甜度为a i 。计算鸭想购买若干颗糖块,来填满自己的糖包。糖包的甜度为填满糖包所有糖块的甜度的乘积;糖包的价值为填满糖包所有糖块的价格的总和; 现在计算鸭想从n个糖块中挑选若干个(至少一个)糖块填充糖包,使其尽可能满足糖包的甜度和价值差的绝对值最小。 输入格式: 输入的第一行给出一个整数n——表示糖块的数量。; 接下来每行两个整数a i ,b i ——表示第i个糖块的甜度和价格。 1≤n≤30 ∑a i ≤10 9 ∑b i ≤10 9 输出格式: 输出一个整数——表示糖包的甜度和价值差的绝对值的最小值。
时间: 2024-04-14 13:29:35 浏览: 36
这个问题可以通过动态规划来解决。首先,我们可以将糖块按照价值从小到大排序,然后定义一个二维数组dp,其中dp[i][j]表示从前i个糖块中选取若干个填充糖包,使其甜度和价值之差的绝对值最小,并且甜度之和不超过j的情况下,甜度和的最大值。
状态转移方程如下:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]] + b[i])
其中a[i]表示第i个糖块的甜度,b[i]表示第i个糖块的价格。
最终的答案即为dp[n][x],其中x表示糖包的甜度和的一半。
下面是一个示例代码实现:
```python
def solve(n, candies):
candies.sort(key=lambda x: x[1]) # 按照糖块的价格从小到大排序
total_sweetness = sum([c[0] for c in candies]) # 糖块的总甜度
target_sweetness = total_sweetness // 2 # 糖包的目标甜度
dp = [[0] * (target_sweetness + 1) for _ in range(n + 1)] # 动态规划数组
for i in range(1, n + 1):
for j in range(1, target_sweetness + 1):
if candies[i-1][0] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-candies[i-1][0]] + candies[i-1][1])
return abs(dp[n][target_sweetness] - (total_sweetness - dp[n][target_sweetness]))
# 读取输入
n = int(input())
candies = []
for _ in range(n):
a, b = map(int, input().split())
candies.append((a, b))
# 调用函数求解并输出结果
print(solve(n, candies))
```
希望能对你有所帮助!如果有任何疑问,请随时提问。