题目描述：
有
n个物品和一个大小为m的背包. 给定数组A表示每个物品的大小和数组V表示每个物品的价值.问最多能装入背包的总价值是多大?
A[i], V[i], n, m均为整数- 你不能将物品进行切分
- 你所挑选的要装入背包的物品的总大小不能超过
m - 每个物品只能取一次
- m <= 1000m<=1000
len(A),len(V)<=100len(A),len(V)<=100
思路分析：
对于每一个物品，它有四种情况：
①价值大，体积大。②价值大，体积小。③价值小，体积大。④价值小，体积小。
因此，在一个背包中，在装入物品的时候，我们需要考虑一种特殊情况和两种常见情况。
特殊情况：装不下。常见情况：放和不放。
我们先定义问题需要的状态：
F(i,j):表示从第i个商品中选择了商品后，大小为j的背包的价值。
状态转移方程：
图中，F中的i是从1开始的，A和V中的i和j是从0开始的。
特殊情况：如果装不下，那么此时的价值和前i-1个情况的价值是一样的，即F(i,j) = F(i-1,j);
如果可以装入：需要在两种选择中找最大的，即F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) V[i]}。
其中，F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值。F(i-1, j - A[i]) V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i个商品。
初始化：第0行和第0列都为0，表示没有装物品时的价值都为0，即F(0,j) = F(i,0) = 0;
返回值：F(n,m);
代码如下：
代码语言：javascript复制int backPackII(int m, vector<int> &a, vector<int> &v) {
// write your code here
if(a.empty() || v.empty() || m< 1)
{
return 0;
}
//多加一行一列，用于设置初始条件
int N = a.size() 1;
int M = m 1;
vector<vector<int>> ret(N,vector<int>(M,0));
for(int i = 1;i<N; i)
{
for(int j = 1;j<M; j)
{
//如果物品的体积大于j，说明放不下了
//那就跟i-1的价值意义
if(a[i-1]>j)
{
ret[i][j] = ret[i-1][j];
}
else //装得下，放或不放
{
//如果不放，那价值也跟i-1的价值一样
//如果放，需要腾出放物品i的空间
ret[i][j] = max(ret[i-1][j],ret[i-1][j-a[i-1]] v[i-1]);
}
}
}
return ret[N-1][m];
}优化：
上面的算法在计算第i行元素时，只用到第i-1行的元素，所以二维的空间可以优化为一维空间。但是如果是一维向量，需要从后向前计算，因为后面的元素更新需要依靠前面的元素未更新（模拟二维矩阵的上一行的值）的值。
代码语言：javascript复制int backPackII(int m, vector<int> A, vector<int> V) {
if (A.empty() || V.empty() || m < 1)
{
return 0;
}
const int N = A.size();
//多加一列，用于设置初始条件，因为第一件商品要用到前面的初始值
const int M = m 1;
vector<int> result;
//初始化所有位置为0，第一行都为0，初始条件
result.resize(M, 0);
//这里商品的索引位置不需要偏移，要和未优化的方法区分开
//这里的i-1理解为上一行，或者未更新的一维数组值
for (int i = 0; i != N; i)
{
for (int j = M - 1; j > 0; --j)
{
//如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
if (A[i] > j)
{
result[j] = result[j];
} //如果可以装下，分两种情况，装或者不装
//如果不装，则即为(i-1, j)
//如果装，需要腾出放第i个物品大小的空间： j - A[i]
// 装入之后的最大价值即为(i - 1, j -A[i - 1]) 第i个商品的价值V[i]
//最后在装与不装中选出最大的价值
else
{
int newValue = result[j - A[i]] V[i];
result[j] = max(newValue, result[j]);
}
}
} //返回装入前N个商品，物品大小为m的最大价值
return result[m];
};
