ly 在战场凹分，没吃午饭，饥肠辘辘的他从文具盒里翻出了一袋饼干...... 这袋饼干有 n 块，分别称作第 1,2...n 块，第 i 块饼干能提供 w [i] 的饱腹感. 有强迫症的 ly 必须从第 1 块开始吃，然后第 2 块... 直到总饱腹感达到（大于或等于）s 时即停止. 众所周知，万事万物都会随着多种因素的变化而变化，当然 ly 的饱腹感上限 s 也不例外 于是 ly 会询问你 q 次：当他的饱腹感上限为 s [i] 时，他需要吃多少块饼干

这是一个典型的背包问题，可以使用动态规划来解决。

定义一个二维数组dp[i][j]，表示当饱腹感上限为j时，前i块饼干最多能提供多少饱腹感。

状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+w[i])

其中，dp[i-1][j]表示不选第i块饼干，dp[i-1][j-w[i]]+w[i]表示选第i块饼干。

最终的答案是最小的满足dp[n][j]>=s[i]的j。

具体实现可以参考以下代码（Python）：

n = int(input())
w = list(map(int, input().split()))

max_s = 1000000
dp = [[0]*(max_s+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, max_s+1):
        dp[i][j] = dp[i-1][j]
        if j >= w[i-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+w[i-1])

q = int(input())
for i in range(q):
    s = int(input())
    j = 1
    while dp[n][j] < s:
        j += 1
    print(j)

时间复杂度为O(n*max_s+q)，可以通过本题。