LintCode-背包问题I、II、III、IV、V、VII、V

I

描述

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

你不可以将物品进行切割。

样例

如果有4个物品[2, 3, 5, 7]

如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。

如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。

函数需要返回最多能装满的空间大小。

挑战

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

代码

体积计算值版本（超时）

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @param V: Given n items with value V[i]
    @return: The maximum value
    """
    
    def backPack(self, m, A):
        # write your code here
        dp = [False for j in range(m+1)]
        for a in A:
            for j in range(m, a-1, -1):
          # for j in reversed(range(a, m+1)):
                dp[j] = max(dp[j], dp[j-a] + a)
        return dp[-1]

两个for循环都超时，Time Limit Exceeded，

for j in range(m, a-1, -1):
for j in reversed(range(a, m+1)):

说明了超时与reversed和range的叠加使用没有关系。这个算法的java代码是可以过的，python通过不了，说明python在数值计算方面的性能还是不及java的。

True Or False版本

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @param V: Given n items with value V[i]
    @return: The maximum value
    """
    
    def backPack(self, m, A):
        # write your code here
        dp = [False for j in range(m+1)]
        dp[0] = True
        result = 0
        for a in A:
            for j in range(m, a-1, -1):
                if dp[j-a] == True:
                    dp[j] = True
                    if j > result:
                        result = j
        return result

使用result记录能达到的最大result，用True Or False来说明上个体积状态是否可以达到，就不会超时。证明了True Or False的赋值过程比起体积的计算赋值在python中性能更好更省时间。

题目来源

https://www.lintcode.com/problem/backpack/description

II

描述

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

A[i], V[i], n, m均为整数。你不能将物品进行切分。你所挑选的物品总体积需要小于等于给定的m。

样例

对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话，最大能够装入的价值为9。

挑战

O(n x m) memory is acceptable, can you do it in O(m) memory?

代码

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @param V: Given n items with value V[i]
    @return: The maximum value
    """
    def backPackII(self, m, A, V):
        # write your code here
        dp = [0 for j in range(m+1)]
        
        for i in range(1, len(A)+1):
            for j in reversed(range(1, m+1)):
                if j < A[i-1]:
                    pass
                else:
                    dp[j] = max(dp[j], dp[j-A[i-1]] + V[i-1])
        return dp[-1]

题目来源

https://www.lintcode.com/problem/backpack-ii/description

III

描述

给定n种具有大小 Ai 和价值 Vi 的物品(每个物品可以取用无限次)和一个大小为 m 的一个背包, 你可以放入背包里的最大价值是多少?

样例

给出四个物品, 大小为 [2, 3, 5, 7], 价值为 [1, 5, 2, 4], 和一个大小为 10 的背包. 最大的价值为 15.

注意事项

你不能将物品分成小块, 选择的项目的总大小应 小于或等于 m

代码

class Solution:
    """
    @param A: an integer array
    @param V: an integer array
    @param m: An integer
    @return: an array
    """

    def backPackIII(self, A, V, m):
        # write your code here
        if len(A) == 0:
            return 0
        dp = [0 for j in range(m + 1)]

        for j in range(1, m + 1):
            for k in range(0, len(A)):
                    if A[k] <= j:
                        dp[j] = max(dp[j], dp[j - 1], dp[j - A[k]] + V[k])
        return dp[-1]

题目来源

https://www.lintcode.com/problem/backpack-iii/description

IV

描述

给出 n 个物品, 以及一个数组, nums[i]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品可以使用无数次

样例

给出候选物品集合 [2,3,6,7] 和 target 7,

一个答案集合为:

[7]
[2,2,3]
返回 2

代码

class Solution:
    """
    @param nums: an integer array and all positive numbers, no duplicates
    @param target: An integer
    @return: An integer
    """
    def backPackIV(self, nums, target):
        # write your code here
        dp = [[0 for j in range(target+1)] for i in range(len(nums))]
        for j in range(target+1):
            if j%nums[0] == 0:
                dp[0][j] = 1
        for i in range(1, len(nums)):
            for j in range(0, target+1):
                if j >= nums[i]:
                    k = j - nums[i]
                    while (k >= 0):
                        dp[i][j] += dp[i - 1][k]
                        k = k - nums[i]
                dp[i][j] += dp[i-1][j]
        return dp[-1][-1]

题目来源

https://www.lintcode.com/problem/backpack-iv/description

V

描述

给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次

样例

给出候选物品集合 [1,2,3,3,7] 以及 target 7

结果的集合为:

[7]
[1,3,3]
返回 2

代码

初始版（超时）

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        dp = [[0 for j in range(target+1)] for i in range(len(nums))]
        for i in range(len(nums)):
            dp[i][0] = 1
        dp[0][nums[0]] = 1
        for i in range(1, len(nums)):
            for j in range(1, target+1):
                if j >= nums[i]:
                    dp[i][j] += dp[i - 1][j-nums[i]]
                dp[i][j] += dp[i-1][j]
        return dp[-1][-1]

但是超时， Time Limit Exceeded， for j in range(1, target+1)浪费了很多无用的时间。

优化时间版（超内存）

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        dp = [[0 for j in range(target+1)] for i in range(len(nums))]
        for i in range(len(nums)):
            dp[i][0] = 1
        dp[0][nums[0]] = 1
        Sum = nums[0]
        for i in range(1, len(nums)):
            Sum += nums[i]
            for j in range(1, min(Sum+1, target+1)):
                if j >= nums[i]:
                    dp[i][j] += dp[i - 1][j-nums[i]]
                dp[i][j] += dp[i-1][j]
        return dp[-1][-1]

这个版本不超时了，但是超内存使用， Memory Limit Exceeded， 说明对于一些case，

dp = [[0 for j in range(target+1)] for i in range(len(nums))] 

开的太大了。

优化内存使用版本A（超时）

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        dp = [[0 for j in range(target+1)] for i in range(2)]
        dp[0][0] = 1
        dp[0][nums[0]] = 1
        Sum = nums[0]
        for i in range(1, len(nums)):
            Sum += nums[i]

            for j in range(0, min(Sum+1, target+1)):
                if j >= nums[i]:
                    dp[1][j] += dp[0][j - nums[i]]
                dp[1][j] += dp[0][j]
            for j in range(0, min(Sum+1, target+1)):
                dp[0][j] = dp[1][j]
                dp[1][j] = 0
        return dp[0][-1]

两行dp循环来使用，但又开始超时了， Time Limit Exceeded，

for j in range(0, min(Sum+1, target+1)):
                dp[0][j] = dp[1][j]
                dp[1][j] = 0

估计是循环赋值增加了一倍时间导致的。

优化内存使用版本B（错误）

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        dp = [0 for j in range(target+1)]
        dp[0] = 1
        Sum = nums[0]
        for i in range(1, len(nums)):
            Sum += nums[i]
            for j in range(1, min(Sum+1, target+1)):
                if j >= nums[i]:
                    dp[j] += dp[j - nums[i]]
        return dp[-1]

使用一行dp来完成，正向遍历，

for j in range(1, min(Sum+1, target+1)):

每次都把上一次的累计方法覆盖掉，但是实际上这是错误的解法， 因为每次更新某个j的状态时涉及到的j-nums[i]状态可能会把自己再使用一次。

优化内存使用版本C（正确）

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        dp = [0 for j in range(target+1)]
        dp[0] = 1
        for i in range(0, len(nums)):
            for j in reversed(range(nums[i], target+1)):
                    dp[j] += dp[j - nums[i]]
        return dp[-1]

最好也是最正确的解法，在优化内存使用版本B的基础上倒过来遍历j就不会把当前nums[i]重复使用了，因为先更新j大的状态， 则更新后面j大的状态时，j-nums[i]<j的状态都还是上一个i的状态。

题目来源

https://www.lintcode.com/problem/backpack-v/description

VII

描述

假设你身上有 n 元，超市里有多种大米可以选择，每种大米都是袋装的，必须整袋购买，给出每种大米的重量，价格以及数量，求最多能买多少公斤的大米

样例

Given:
n = 8
prices = [2,4]
weight = [100,100]
amounts = [4,2]

Return:400

代码

class Solution:
    """
    @param n: the money of you
    @param prices: the price of rice[i]
    @param weight: the weight of rice[i]
    @param amounts: the amount of rice[i]
    @return: the maximum weight
    """
    def backPackVII(self, n, prices, weight, amounts):
        # write your code here
        dp = [0 for j in range(n+1)]
        
        for i in range(0, len(prices)):
            for k in range(0, amounts[i]):
                for j in range(n, prices[i]-1, -1):
                    dp[j] = max(dp[j], dp[j-prices[i]]+weight[i])
        return dp[-1]                    

轻松过，很OK。

题目来源

https://www.lintcode.com/problem/backpack-vii/description

VIII

给一些不同价值和数量的硬币。找出这些硬币可以组合在1 ~ n范围内的值

样例

Given:
n = 10
value = [1,2,4]
amount = [2,1,1]

Return: 8
They can combine all the values in 1 ~ 8

代码

class Solution:
    """
    @param n: the value from 1 - n
    @param value: the value of coins
    @param amount: the number of coins
    @return: how many different value
    """
    def backPackVIII(self, n, value, amount):
        # write your code here
        dp = [False for j in range(n+1)]
        result = 0
        dp[0] = True
        for i in range(0, len(value)):
            cnt = [0 for j in range(n+1)]
            for j in range(value[i], n+1):
                if dp[j] is not True and dp[j-value[i]] is True and cnt[j-value[i]] < amount[i]:
                    dp[j] = dp[j-value[i]]
                    result += 1
                    cnt[j] = cnt[j-value[i]] + 1
        return result

cnt用来记录每套相同价值的多数量硬币的使用次数，需要在这里特别说明的是此问题对比背包问题I， 因为他们都是计算通过True和False的方式来记录是否能达到背包空间使用了j数量，但用法有特异性。
背包问题I为了节省空间，dp是一维数组，并且j是从后往前遍历的，为什么？
因为如果从前往后遍历，当j=2*value[i]时，j-value[i]=value[i]，那么同一个石头就被用使用两次，而题目定义中石头仅有一个，所以就错误了。
而背包问题VII中的j只能从前往后遍历，为什么？
因为只有从前往后遍历，cnt才能通过j-value[i]状态的数值知道当前j状态的数值，那么为什么不会错误，因为这个题目定义中某一类硬币是有多个的， 并且cnt[j-value[i]]会和amount[i]做对比，保证硬币的使用是合乎逻辑，也就是足够用的。

题目来源

https://www.lintcode.com/problem/backpack-viii/description

IX

你总共有10 * n 千元(n万元 )，希望申请国外的大学，要申请的话需要交一定的申请费用，给出每个大学的申请费用以及你得到这个大学offer的成功概率，大学的数量是 m。如果经济条件允许，你可以申请多所大学。找到获得至少一份工作的最高可能性。

样例

给定:
n = 10
prices = [4,4,5]
probability = [0.1,0.2,0.3]

返回:0.440

注意事项

0<=n<=10000,0<=m<=10000

代码

class Solution:
    """
    @param n: Your money
    @param prices: Cost of each university application
    @param probability: Probability of getting the University's offer
    @return: the  highest probability
    """
    def backpackIX(self, n, prices, probability):
        # write your code here
        for i in range(len(probability)):
            probability[i] = 1 - float(probability[i])
            
        dp = [1 for j in range(n+1)]
        
        for i in range(1, len(prices)+1):
            for j in range(n, prices[i-1]-1, -1):
                dp[j] = min(dp[j], dp[j-prices[i-1]]*probability[i-1])
        return 1-dp[-1]

我感觉这个题目的case有些简单。

题目来源

https://www.lintcode.com/problem/backpack-ix/description

X

你总共有n元，商人总共有三种商品，它们的价格分别是150元,250元,350元，三种商品的数量可以认为是无限多的，购买完商品以后需要将剩下的钱给商人作为小费，求最少需要给商人多少小费

样例

给定: n = 900
返回: 0

代码

class Solution:
    """
    @param n: the money you have
    @return: the minimum money you have to give
    """
    def backPackX(self, n):
        # write your code here
        dp = [False for j in range(n+1)]
        dp[0] = True
        result = 0
        for money in (150, 250, 350):
            for j in range(money, n+1):
                if dp[j] is not True and dp[j-money] is True:
                    dp[j] = True
                    if j > result:
                        result = j
        return n-result

简单题目，使用True or False最节省时间空间，可以参考背包问题I。

for j in range(money, n+1):

一定要从money而不是1开始，否则j-money<0会使得dp[j-money]出现dp[-n]的结果。

题目来源

https://www.lintcode.com/problem/backpack-x/description