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]的结果。
