各位大佬，有知道今天晚上阿里模拟笔试的编程题怎么做的吗？

完全背包，积分变成容量，最大价值变成最小期望值，每个福的期望值为概率的倒数。

每张福卡的积分*概率 = 每扫一次这种福卡能拿到的积分的期望。 然后应该贪心就可以了 我做的不是这题，不知道这样的想法对不对 样例： 100 * 0.5 = 50, 100 * 1.0 / 50 = 2.0

这道题和换零钱问题（https://www.nowcoder.com/questionTerminal/185dc37412de446bbfff6bd21e4356ec）相似 不同的地方在于加入了几何分布，且dp[i][j]的意义变成了达到金钱j所需要的最小扫描次数。 今天才写的代码，有问题还望大家指出 #coding=utf-8 from __future__ import division class MininumScan:     def count_scans(self, changes, scans, n, x):         """利用动态规划来求最小扫描次数，动态递归分两层，一层是是否使用零钱列表中的下一个零钱种类；            一层是使用一次某种零钱后，期望金额的变化"""         if n == 0:             return -1         dp = [[-1 for i in range(x + 1)] for j in range(n)] # 初始化二维列表， -1表示凑不出这个金额         for i in range(n):             dp[i][0] = 0 # 凑出0需要0次扫描         for j in range(1, x + 1):             if j % changes[0] == 0:                 dp[0][j] = (j / changes[0]) * scans[0] # 金额是changes[0]的整数倍才可能凑出来         for i in range(1, n):             for j in range(1, x + 1):                 # 计算使用changes[i]的扫描情况                 if j - changes[i] >= 0 and dp[i][j - changes[i]] != -1:                     tmp = dp[i][j - changes[i]] + scans[i]                 else:                     tmp = -1                 # 递推，核心部分                 if tmp == -1:                     dp[i][j] = dp[i - 1][j]                 else:                     if dp[i - 1][j] == -1:                         dp[i][j] = tmp                     else:                         dp[i][j] = min(tmp, dp[i - 1][j])         return dp[n - 1][x] test = MininumScan() line = raw_input() scores = [int(x) for x in line.split(' ')] expect_num = int(raw_input()) line = raw_input() pros = [float(x) for x in line.split(' ')] scans = [1 / x for x in pros] # 扫出某张福卡的期望次数 n = len(changes) print(test.count_scans(scores, scans, n, expect_num))

不是很懂题目，是不是先要求多元一次方程 af1+bf2+cf3+df4+ef5=N 是否有整数解 然后用贪心求次数

必须用Python 吗

直接dp就行了…

个人想法是 获得一张福卡的积分的期望次数是1/p，然后排列组合到目标积分找到最小次数。不过这个想法并没有运行

我没看懂这道题。。。

兄弟，你选的什么岗位啊，我的编程题就是一道类似于字符串去重的问题