小苯的粉丝关注_小红书笔试题

Python

jys1221

将整个问题转换为正好装满的0-1背包问题，尝试所有方案找到最小值

n,x=map(int,input().split())
acc=list(map(int,input().split()))
d=[i//2 for i in acc]
def backpack(n,x,d):
    dp=[float('inf')]*(x+1)
    dp[0] = 0
    for i in range(n):
        for j in range(x,d[i]-1,-1):
            if dp[j-d[i]]!=float('inf'):
                dp[j]=min(dp[j],dp[j-d[i]]+1)
    return dp[x]
cases=[]
cases.append(backpack(n,x,d))        #不多次宣传
for i in range(n):
    d[i]=acc[i]                      #第i个账号多次宣传
    cases.append(backpack(n,x,d))
    d[i]=acc[i]//2                   #回溯
ans=min(cases)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

发表于 2025-08-20 14:57:15 回复(0)

Python

郁闷的艾伦在做核酸

# -*- coding: utf-8 -*-

import sys

from functools import lru_cache

def main():

sys.setrecursionlimit(1 << 25)

n = int(sys.stdin.readline())

a = list(map(int, sys.stdin.readline().split()))

x = int(sys.stdin.readline())

b = [num // 2 for num in a]

b_sorted = sorted(b, reverse=True)

total_b = sum(b)

min_case1 = float('inf')

# 处理情况1：不使用多次推荐

def dfs_case1(pos, current_sum, count):

nonlocal min_case1

if current_sum == x:

if count < min_case1:

min_case1 = count

return

if pos >= len(b_sorted) or current_sum > x:

return

remaining_sum = sum(b_sorted[pos:])

if current_sum + remaining_sum < x:

return

# 剪枝：如果当前已经不可能更优

if count >= min_case1:

return

# 选当前元素

dfs_case1(pos + 1, current_sum + b_sorted[pos], count + 1)

# 不选当前元素

dfs_case1(pos + 1, current_sum, count)

dfs_case1(0, 0, 0)

# 处理情况2：使用一次多次推荐

min_case2 = float('inf')

for k in range(n):

ak = a[k]

if ak > x:

continue

s = x - ak

if s < 0:

continue

# 构造其他元素的b数组，排除k

other_b = [b[i] for i in range(n) if i != k]

other_sorted = sorted(other_b, reverse=True)

# 提前剪枝：总和不足

if sum(other_sorted) < s:

continue

# 使用DFS找最少数目

min_m = float('inf')

def dfs_case2(pos, curr, cnt):

nonlocal min_m

if curr == s:

if cnt < min_m:

min_m = cnt

return

if pos >= len(other_sorted) or curr > s:

return

remaining = sum(other_sorted[pos:])

if curr + remaining < s:

return

if cnt >= min_m:

return

# 选当前元素

dfs_case2(pos + 1, curr + other_sorted[pos], cnt + 1)

# 不选

dfs_case2(pos + 1, curr, cnt)

dfs_case2(0, 0, 0)

if min_m != float('inf'):

total = 1 + min_m

if total < min_case2:

min_case2 = total

# 确定最终结果

res = float('inf')

if min_case1 != float('inf'):

res = min_case1

if min_case2 != float('inf'):

res = min(res, min_case2)

print(res if res != float('inf') else -1)

if __name__ == "__main__":

main()

发表于 2025-04-19 11:43:59 回复(0)

提交观点

小苯的粉丝关注

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题