七十九天-背包问题，Spring

学习笔记：

1.Application Context 是 BeanFactory 的子接口，也被称为 Spring 上下文。

2.Application Context 是 spring 中较高级的容器。和 BeanFactory 类似，它可以加载配置文件中定义的 bean，将所有的 bean 集中在一起，当有请求的时候分配 bean。 另外，它增加了企业所需要的功能，比如，从属性文件中解析文本信息和将事件传递给所指定的监听器。

3.最常被使用的 ApplicationContext 接口实现：

FileSystemXmlApplicationContext：该容器从 XML 文件中加载已被定义的 bean。在这里，你需要提供给构造器 XML 文件的完整路径。

ClassPathXmlApplicationContext：该容器从 XML 文件中加载已被定义的 bean。在这里，你不需要提供 XML 文件的完整路径，只需正确配置 CLASSPATH 环境变量即可，因为，容器会从 CLASSPATH 中搜索 bean 配置文件。

WebXmlApplicationContext：该容器会在一个 web 应用程序的范围内加载在 XML 文件中已被定义的 bean。

4.构成每个 bean 定义的下列属性

5.Bean 与 Spring 容器的关系

6.Spring 框架支持以下五个作用域，分别为 singleton、prototype、request、session 和 global session，5种作用域说明如下所示

7.Singleton 是单例类型，就是在创建起容器时就同时自动创建了一个 bean 的对象，不管你是否使用，他都存在了，每次获取到的对象都是同一个对象。注意，Singleton 作用域是 Spring 中的缺省作用域。

8.Prototype 是原型类型，它在我们创建容器的时候并没有实例化，而是当我们获取bean的时候才会去创建一个对象，而且我们每次获取到的对象都不是同一个对象。

9.Bean 的生命周期，当一个 bean 被实例化时，它可能需要执行一些初始化使它转换成可用状态。同样，当 bean 不再需要，并且从容器中移除时，可能需要做一些清除工作。

10.Bean的生命周期可以表达为：Bean的定义——Bean的初始化——Bean的使用——Bean的销毁

11.bean 定义可以包含很多的配置信息，包括构造函数的参数，属性值，容器的具体信息例如初始化方法，静态工厂方法名，等等。子 bean 的定义继承父定义的配置数据。子定义可以根据需要重写一些值，或者添加其他值。

12.Spring Bean 定义的继承与 Java 类的继承无关，但是继承的概念是一样的。你可以定义一个父 bean 的定义作为模板和其他子 bean 就可以从父 bean 中继承所需的配置。当你使用基于 XML 的配置元数据时，通过使用父属性，指定父 bean 作为该属性的值来表明子 bean 的定义。

13.Spring框架的核心功能之一就是通过依赖注入的方式来管理Bean之间的依赖关系。

14.背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：

01背包问题

完全背包问题

多重背包问题

15.0-1背包问题优化：使用两个大小为C的数组来存储当前状态和上一行的状态，空间复杂度为O（C）

16.0-1背包问题优化2：使用一个大小为C的数组来存储当前的状态，下一行的状态从右到左依次更新，空间复杂度为O（C）

17.完全背包问题：每个物品可以无限使用。多重背包问题：每个物品不只一个，有num(i)个

完全背包问题状态转移方程：dp[i][j] = max(dp[i?1][j], dp[i][j?w[i]]+v[i]) // j >= w[i]

18.多维费用背包问题：要考虑物品的体积和重量两个维度

多重背包问题状态转移方程：# k为装入第i种物品的件数, k <= min(n[i], j/w[i])

dp[i][j] = max{(dp[i-1][j ? k*w[i]] + k*v[i]) for every k}

19.用户模块开发