01背包问题（思路与python代码）

①===========题目

②==========思路

• 

•  

  

• 最好是单位换算更精确（都正整数是为了编程方便，不然数组索引是小数就寄了）

  

•  

  

③==========python代码

import numpy as np
import pandas as pd

pf = [540, 200, 180, 350, 60, 150, 280, 450, 320, 120]  # 10个物体的利润
w = [6, 3, 4, 5, 1, 2, 3, 5, 4, 2]  # 10个物体的重量
W = 30  # 背包最大负重

FF = [[0 for i in range(W)] for j in range(len(pf))]  # DP二维数组。FF


def initialize():
    # 初始化第一列
    MAX = 0
    for i in range(len(FF)):
        if w[i] == 1 and FF[i - 1][0] < pf[i]:
            MAX = pf[i]
            FF[i][0] = MAX
        else:
            FF[i][0] = MAX

    # 初始化第一行
    FF[0][w[0] - 1:] = [pf[0] for _ in range(len(FF[0][w[0]:]) + 1)]


def dynamic():
    for j in range(1, W):  # j+1的空间
        for i in range(1, len(pf)):  # 前i+1个物品
            if w[i] > j + 1:  # 如果只放这个新物品都放不下（别忘了这里的w[i]是真实的，而j是少了个1的）
                FF[i][j] = FF[i - 1][j]
            elif w[i] == j + 1:
                FF[i][j] = max(FF[i - 1][j], pf[i])
            else:
                FF[i][j] = max(FF[i - 1][j], pf[i] + FF[i - 1][j - w[i]])


if __name__ == '__main__':
    initialize()
    dynamic()
    # 打印结果
    df = pd.DataFrame(FF)
    df.columns = df.columns + 1
    df.index = df.index + 1
    print(df)