你在一家家具公司工作，需要将家具发往全国各地，为此，你需要将箱子装上卡车，每个箱子的尺寸和价值各不相同，你需要尽可能利用每辆卡车的空间，假设卡车空间大小为K，给定一个数组W，它的第i个元素表示第i个箱子的尺寸，给定一个数组V，它的第i个元素表示第i个箱子的价值，为此，你将如何选择要装上卡车的箱子在满足卡车的空间占用最大的前提下，是卡车运输的箱子总价值最大？
输入描述
参数1：卡车空间K（1<K<1000）
参数2：箱子个数N（1<N<1000）
参数3：每个箱子尺寸w（1<w<1000）
参数4：每个箱子价值v（1<v<1000）
输出描述
在满足卡车的空间占用最大的前提下，使卡车运输的箱子总价值最大？输出卡车运输的箱子最大的总价值。
示例1
输入
9
5
2 2 4 6 3
3 4 8 9 6
输出
18
思路：用动态规划算法
1、不放第n个物品，此时总价值为F(i−1,j)
2、放置第n个物品，此时总价值为F(i−1,j−Wi)+Pi
两种选择中总价值最大的方案就是我们的最终方案，状态转移方程：f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
#include<iostream> #include<vector> #include<algorithm> using namespace std; int fun(int n, int v, vector<int> weight, vector<int> price, vector<vector<int>> res) { for (int i = 1;i <= n;++i) { for (int j = 1;j <= v;++j) { if (weight[i] > j) //选择物品i时，总重量超出了范围，则不放入第i件 res[i][j] = res[i - 1][j]; else res[i][j] = max(res[i - 1][j - weight[i]] + price[i], res[i - 1][j]); //反之，放入第i件 } } return res[n][v]; //告诉主函数，这个子函数运行的结果 } int main() { int n, v; cin >> v >> n; //输入数据：v为卡车空间，n为箱子的个数 vector<int> weight(n + 1, 0); vector<int> price(n + 1, 0); vector<vector<int>> res(n + 1, vector<int>(v + 1, 0)); //定义数组和矩阵 for (int i = 1;i <= n;++i) { cin >> weight[i]; } for (int i = 1;i <= n;++i) { cin >> price[i]; } //输入数据：weight为每个箱子的重量，price为每个箱子的价值 int ans = fun(n, v, weight, price, res); cout << ans << endl; //输出 return 0; //告诉操作系统，自身正常运行结束 }我们再来看这个问题。我们需要选择n个元素中的若干个来形成最优解，假定为k个。那么对于这k个元素a1, a2, ...ak来说，它们组成的物品组合必然满足总重量<=背包重量限制，而且它们的价值必然是最大的。因为它们是我们假定的最优选择嘛，肯定价值应该是最大的。假定ak是我们按照前面顺序放入的最后一个物品。它的重量为wk，它的价值为vk。既然我们前面选择的这k个元素构成了最优选择，如果我们把这个ak物品拿走，对应于k-1个物品来说，它们所涵盖的重量范围为0-(W-wk)。假定W为背包允许承重的量。假定最终的价值是V，剩下的物品所构成的价值为V-vk。这剩下的k-1个元素是不是构成了一个这种W-wk的最优解呢？
我们可以用反证法来推导。假定拿走ak这个物品后，剩下的这些物品没有构成W-wk重量范围的最佳价值选择。那么我们肯定有另外k-1个元素，他们在W-wk重量范围内构成的价值更大。如果这样的话，我们用这k-1个物品再加上第k个，他们构成的最终W重量范围内的价值就是最优的。这岂不是和我们前面假设的k个元素构成最佳矛盾了吗？所以我们可以肯定，在这k个元素里拿掉最后那个元素，前面剩下的元素依然构成一个最佳解。
现在我们经过前面的推理已经得到了一个基本的递推关系，就是一个最优解的子解集也是最优的。可是，我们该怎么来求得这个最优解呢？我们这样来看。假定我们定义一个函数c[i, w]表示到第i个元素为止，在限制总重量为w的情况下我们所能选择到的最优解。那么这个最优解要么包含有i这个物品，要么不包含，肯定是这两种情况中的一种。如果我们选择了第i个物品，那么实际上这个最优解是c[i - 1, w-wi] + vi。而如果我们没有选择第i个物品，这个最优解是c[i-1, w]。这样，实际上对于到底要不要取第i个物品，我们只要比较这两种情况，哪个的结果值更大不就是最优的么？
在前面讨论的关系里，还有一个情况我们需要考虑的就是，我们这个最优解是基于选择物品i时总重量还是在w范围内的，如果超出了呢？我们肯定不能选择它，这就和c[i-1, w]一样。
另外，对于初始的情况呢？很明显c[0, w]里不管w是多少，肯定为0。因为它表示我们一个物品都不选择的情况。c[i, 0]也一样，当我们总重量限制为0时，肯定价值为0。
这样，基于我们前面讨论的这3个部分，我们可以得到一个如下的递推公式：
有了这个关系，我们可以更进一步的来考虑代码实现了。我们有这么一个递归的关系，其中，后面的函数结果其实是依赖于前面的结果的。我们只要按照前面求出来最基础的最优条件，然后往后面一步步递推，就可以找到结果了。
我们再来考虑一下具体实现的细节。这一组物品分别有价值和重量，我们可以定义两个数组vector<int>price, vector<int>weigh。price[i]表示第i个物品的价值，weigh[i]表示第i个物品的重量。为了表示c[i, w]，我们可以使用一个vector<vector<int>>res(n+1,vector<int>(v+1),0)的矩阵。其中i的最大值为物品的数量，而w表示最大的重量限制。按照前面的递推关系，res[i][0]和res[0][w]都是0。而我们所要求的最终结果是res[n][w]。所以我们实际中创建的矩阵是(n + 1) x (w + 1)的规格。
