backpacks
backpack01_float_dy
参考: https://my.oschina.net/u/3242615/blog/1940533/
backpack01_float_dy
- dramkit.backpacks.backpack01_float_dy.backpack01_float_dy(c, v, w)
动态规划解决（正）浮点数0-1背包问题
- Parameters:
c (float) – 背包最大容量
v (list) – 物品价值列表
w (list) – 物品重量列表
- Returns:
max_v (float) – 最大价值
trace (list) – 最大价值解对应物品编号（从0开始计）
c_v (list) – 最大容量-最大价值跳跃点完整记录
Note
c_v[_] = [W, V]表示某个物品加入之后，最大容量为W时最大价值为V
backpack01_float_dy_smp
- dramkit.backpacks.backpack01_float_dy.backpack01_float_dy_smp(c, v, w)
动态规划解决（正）浮点数0-1背包问题，只输出最大价值，不考虑路径回溯
- Parameters:
c (float) – 背包最大容量
v (list) – 物品价值列表
w (list) – 物品重量列表
- Returns:
max_v – 最大价值
- Return type:
float
backpack01_int_dy
参考:
backpack01_int_dy
- dramkit.backpacks.backpack01_int_dy.backpack01_int_dy(c, v, w)
- 动态规划解决（正）整数0-1背包问题缺点: 只能求解正整数情况
- Parameters:
c (int) – 背包最大容量
v (list) – 物品价值列表
w (list) – 物品重量列表
- Returns:
max_v (float) – 最大价值
trace (list) – 最大价值解对应物品编号（从0开始计）
v_mat (np.ndarray) – 完整价值矩阵
Note
v_mat[i, j]表示在总容量为j的情况下， 在从第i至n（所有物品个数）个物品中选择物品放入时的最大价值
backpack01_int_dy_smp
- dramkit.backpacks.backpack01_int_dy.backpack01_int_dy_smp(c, v, w)
- 动态规划解决（正）整数0-1背包问题，只输出最大价值，不考虑路径回溯缺点: 只能求解正整数情况
- Parameters:
c (int) – 背包最大容量
v (list) – 物品价值列表
w (list) – 物品重量列表
- Returns:
max_v (float) – 最大价值
values (list) – 最大价值变化过程（相当于
dramkit.backpacks.backpack01_int_dy.backpack01_int_dy()函数中v_mat的第一行）Note
values[j]表示总容量为j的情况下可装物品的最大价值
backpack01_float_dy
- dramkit.backpacks.backpack01_int_dy.backpack01_float_dy(c, v, w)
backpack01_float_dy_smp
- dramkit.backpacks.backpack01_int_dy.backpack01_float_dy_smp(c, v, w)
- 利用整数方法通过乘数F改造解决浮点数背包问题，只输出最大价值，不考虑路径回溯