背包问题指这样一类问题，题意往往可以抽象成：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
维基百科
部分背包问题和0/1背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有
If for each item the profit and weight are equal, we get the subset sum problem
Given a set of N (N≤40) integers each of them is at most 1012 determine the largest sum subset having sum less than or equal S (S≤1018)
遗传算法的基本运算过程如下： [2]
（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 [2]
（2）个体评价：计算群体P(t)中各个个体的适应度。 [2]
（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 [2]
（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。 [2]
（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。 [2]
（6）终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 [2]
遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。 [1]
构造出S>M1,M2,Mn>T的图信息,求解旅行商问题
不是最优解
minimalSteps.cpp
| $O_1$ | $O_2$ | $O_3$ | … | $O_{m-1}$ | $O_{m}$ | T | |
|---|---|---|---|---|---|---|---|
| S | … | ||||||
| $M_1$ | … | ||||||
| $M_2$ | … | ||||||
| … | … | … | … | … | … | … | … |
| $M_{n-1}$ | … | ||||||
| $M_{n}$ | … |
| S | $M_1$ | $M_2$ | … | $M_{n-1}$ | $M_{n}$ | |
|---|---|---|---|---|---|---|
| S | 0 | … | ||||
| $M_1$ | … | |||||
| $M_2$ | … | |||||
| … | … | … | … | … | … | … |
| $M_{n-1}$ | … | |||||
| $M_{n}$ | … |
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
时间复杂度$O(n^2)$
