#!/usr/bin/env python
# coding:utf-8

"""
01背包
    每个物品只能选择取或不取，即只能取 0个 或 1个。
"""

# ================================================================================
"""
《算法图解》中的背包问题
"""
"""
假设你是个小偷，背着一个可装4磅东西的背包。
可盗窃的物品有：
物品：吉他，音箱，电脑，手机
重量：1，4，3，1
价值：1500，3000，2000，2000
为了让盗窃的物品价值最高，应该选择哪些物品？
"""


n = 4  # 物品数量
m = 4  # 背包容量
w = [1, 4, 3, 1]  # 重量数组
v = [1500, 3000, 2000, 2000]  # 价值数组


def knapsack_dp(w, v, n, m):
    # 矩阵尺寸: n * (m+1)
    # dp[i][j] 表示在前 i 个物品中，能够装入容量为 j 的背包中的最大价值
    dp = [[0 for _ in range(m + 1)] for _ in range(n)]
    # 计算dp数组第一行[边界]
    for j in range(m + 1):
        if j >= w[0]:
            dp[0][j] = v[0]
            pass
        pass
    # 计算dp数组剩余部分
    for i in range(1, n):
        for j in range(1, m+1):
            print '------------------------------'
            if j >= w[i]:
                dp[i][j] = max(
                    dp[i-1][j],  # 不要当前物品 i
                    dp[i-1][j-w[i]] + v[i]  # 要当前物品 i
                )
            else:
                dp[i][j] = dp[i-1][j]  # 不要当前物品 i
                pass
            print '------------------------------'
            pass
        pass
    print '------------------------------'
    for x in dp:
        print x
        pass
    print '------------------------------'
    return dp[-1][-1]


print '背包承载的最大价值:'
print knapsack_dp(w, v, n, m)
"""
[0, 1500, 1500, 1500, 1500]
[0, 1500, 1500, 1500, 3000]
[0, 1500, 1500, 2000, 3500]
[0, 2000, 3500, 3500, 4000]
"""
# ================================================================================
"""
01背包
    状态转义方程:
        dp[i][j] = max(
            dp[i-1][j],
            dp[i-i][j-w[i]] + v[i]
        )
"""
"""
背包问题 FAQ
    每次迭代时，最大价值不可能降低；
    行的排列顺序发生变化，结果不变；
    无法处理只拿走物品一部分的情况（要么拿走整件物品，要么不拿）（这种情况应该用贪婪算法）；
    无法处理子问题相互依赖的情况（动态规划要求，每个子问题都是离散的，不依赖于其他子问题）；
    最终解可能包含2件以上的商品，但实际上最多只需要合并2个子背包，不会涉及2个以上的子背包；
    最终解可能导致背包没有装满；
"""
# ================================================================================
# ================================================================================
# ================================================================================
# ================================================================================
