猴子摘水果

题目描述

假设果园中有N（1≤N≤100）种水果。猴子想要采摘一些水果带回家，但猴子采摘水果的总重量不能超过W（1≤W≤1000）。

已知每种水果的最大采摘数量Ni（1≤Ni≤100）、每种水果单个的重量Wi（1≤Wi≤100）以及每种水果单个的维生素含量Vi（1≤Vi≤100）。在采摘水果的总重量不超过W的情况下，猴子最多可以获得多少维生素。

例如：N = 3，W = 5，表示有3种水果，且猴子采摘水果的总重量不能超过5。

每种水果的最大采摘量Ni、每种水果单个的重量Wi及每种水果单个的维生素含量Vi，如下表：

第一种水果拿3个，第二种水果拿1个，第三种水果不拿，总体积为5，最大可获得维生素含量为3 * 2 + 4 * 1 = 10。

输入描述

第一行输入两个正整数表示N，W，数字之间以空格隔开

接下来N行，每行输入3个正整数，分别表示Ni，Wi，Vi，数字之间以空格隔开

输出描述

输出一个数，表示在采摘水果的总重量不超过W的情况下，猴子最多可以获得多少维生素

样例输入

3 5

4 1 2

1 2 4

2 1 1

样例输出

10

代码详解

展开查看

N, W = [int(i) for i in input().split()]
Ni = []
Wi = []
Vi = []
for i in range(N):
    ls = [int(i) for i in input().split()]
    Ni.append(ls[0])
    Wi.append(ls[1])
    Vi.append(ls[2])

F = [0 for i in range(0, W+1)]

def CompleteBackPack(w, v):
    for i in range(w, W + 1):
        F[i] = max(F[i], F[i-w] + v)

def OneZeroBackPack(w, v):
    for i in range(W, w -1, -1):
        F[i] = max(F[i], F[i-w] + v)def MultipleBackPack(w, v, n):
    if w * n >= W:
        CompleteBackPack(Wi[i], Vi[i])
        return
    temp_n = 1
    while temp_n < n:
        OneZeroBackPack(temp_n * w, temp_n * v)
        n -= temp_n
        temp_n *= 2
    OneZeroBackPack(n * w, n * v)

for i in range(0, N):
    MultipleBackPack(Wi[i], Vi[i], Ni[i])

print(F[W])

运行结果

展开查看