|
小明有N元钱去药店买口罩，药店里有6个品牌的口罩，A品牌2个装（2元），B品牌3个装（2元）、C品牌1个装（3元）、D品牌5个装（1元），E品牌4个装（5元），F品牌3个装（2元），由于限购每个品牌最多只能买一个，小明最多能买多少口罩？
话不多说先放代码
n=int(input())
res=0
dp=[[0 for i in range(n+1)] for j in range(7)]
mask=[(2,2),(3,2),(1,3),(5,1),(4,5),(3,2)]
for i in range(1,7):
for j in range(1,n+1):
if j>=mask[i-1][1]:
dp[i][j]=max(dp[i-1][j],mask[i-1][0]+dp[i-1][j-mask[i-1][1]])
else:
dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
这个题目看似是基于贪心算法的思想，每次花钱尽可能的挑性价比最高的口罩。但是这种情况会出现一种特殊状况，既若买完D、B、F后剩余5元，按照贪心算法的思想，此时购入性价比最高的A口罩，但是这样就会导致买完A口罩后剩下的3元。贪心思想导致程序依旧选择剩余口罩中性价比最高的E口罩，但很显然E口罩价值5元无法购买。至此算法终止，但很明显这样操作不如直接在剩余5元时直接购入E口罩。
因此，这题的真正解法应该是采用动态规划的思想，这是一个典型的0-1背包问题。
为了方便描述我们以1-6号表示A-F品牌口罩
我们以dp[i][j]记录当手头有j块钱时，面对1-i号口罩时能买到的最多的口罩。我们从左上到右下更新dp数组，当面对i号口罩的价格超出j块钱时，无论如何都无法购入，所以这种情况和面对1-（i-1）既dp[i-1][j]时的最大数量相同；当i号口罩价格少于j块钱时，我们是可以购买的，但是可能需要舍弃之前买入的口罩为i号口罩留下足够的资金，此时我们就要衡量是砸锅卖铁买i号口罩，还是不要他。如果要他，那此时的口罩总量为mask[i-1][0]+dp[i-1][j-mask[i-1][1]]，既第i号口罩数量加上砸锅卖铁后剩下的口罩数量；如果不要那就和买不起的时候一样，为dp[i-1][j]
更新完毕后，最终结果就在dp[6][n],n是我们的初始资金
|