01背包问题和完全背包问题（动态规划的理解）
如题，这是用动态规划来解决。本篇博客核心意在讲明动态规划这个思维。
什么是动态规划？
我将其理解成一种递归，也就是实际上动态规划依然是一种递归，但是其是一种记忆式递归。
如同数列一样: A(n) = Func(An…0)(也就是探究第n项和前面n-1项之间的关系。这实际上就是一种递归式子。)
而动态规划实际就是在这个基础上，衍生出来的解决问题的办法。其核心思维就是记录前面项（可能是一项到n项，可能是n^2项等等），然后在计算n项时直接根据记录计算出前面n项。
理解上述要点，那么动态规划的核心电就在于两个。
1. 动态规划需要找到一个前后项关系，对于程序员而言，就是对于递增的下标之间有锁关联，才能使用动态规划。
2.再者就是这前后的关系是如何的，对应数列就是数列的递归表达式是如何的。用程序员的话就是状态转移方程是如何的。
接下来来看问题。
已知一个背包最多能容纳体积之和为v的物品
现有 n 个物品，第 i 个物品的体积为 vi , 重量为 wi
求当前背包最多能装多大重量的物品?
我一开始遇见这个问题时，完全没有想法，因为从未学过算法，现在让我们了解上面思想后来分析这个问题。
首先来分析这个前后项的问题，如何分析呢?其实题目中就有了，我们把物品序号作为递增的序号，那么是不是就以此作为物品的前后关系即可。
然后就是体积，这也是这种动态规划最难的地方，为什么体积也要作为递增的序列号呢？因为动态规划的核心就是记忆式递归，我们要求的是重量，那么显然最终作为结果需要每步记忆的就是重量，而对应的其他要素其实往往都转化成前后关系，用程序员的话说就是下标之间的关系
也就是说动态规划而言，受影响最终需要求的结果一般作为被记忆的每次结果，其他影响的因素就作为 前后关系变化的Index ，也就是下标。
我们知道对记忆化结果影响因素 是两个物品和 体积。 也就是式子变成了 F(Xn,Yn) = F(Xn-1…X1,Yn-1…Y1)
接着我们理解题目，来总结出上面个式子就可以了。
我们假设，X是物品递增，Y是背包容积递增。在没有物品时，背包自然能装物品就是0；在容积为0时，同样也是0.
那么对于第 Xi物品 和Yj容积呢？ 是不是就看要不要放入这个Xi物品，对吧。
首先看Yj是否能放下，如果Xi物品的容积能放下，加上Yj-V(Xi)容积和Xi-1物品时就能算出放入此物品时的容积。而我们前面毫无疑问记忆了这个结果的。然后我们不妨此物品，是不是就等同于 在只有前i-1个物品来 来放置，也就是 Xi-1和Yj的值，前面也有。如此两个比较取大是不是就达成目的。
当然若Yj根本放不下，那么直接取 Xi-1和Yj处的值就可以。
最后总结出来的式子就是 F(Xi ,Yj) = MAX(F(Xi-1,Yj),F(Xi-1,Yj - V(Xi) + W(Xi));
最后将其总结成代码即可。
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算01背包问题的结果
* @param V int整型 背包的体积
* @param n int整型 物品的个数
* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
* @return int整型
*/
int knapsack(int V, int n, vector<vector<int> >& vw) {
//逐渐思考体积的增长
vector<vector<int>>arr(n,vector<int>(V+1,0));
for(int i = 0;i<=V;i++)
{
if(i>= vw.front().front())
{
arr[0][i] = vw.front().back();
}
}
for(int i = 1;i<n;i++)
{
int iv = vw[i].front();
int iw = vw[i].back();
for(int j = 0;j<=V;j++)
{
arr[i][j] = arr[i-1][j];
if(j>iv)
{
arr[i][j] = max(arr[i-1][j-iv] + iw,arr[i][j]);
}
}
}
return arr.back().back();
}
};
这个问题的第二问是，若恰好装满，那最大容量是多少？
一样的理解，问题没有变化太受影响的需求 和 需要作为下标的因素都没改变 。只是对于每一个式子而言，如Xi Yj不能恰好是0，不满足条件那么我们就认为其是非法的，后序也不能使用。
F(Xi ,Yj) = MAX(F(Xi-1,Yj),F(Xi-1,Yj - V(Xi)) + W(Xi));
也就是上述式子需要做一个修改，对于到Xi号物品，和Yj容积的时候，如果要放入此物品，那么就得看 F(Xi-1,Yj - V(Xi))其的容积是否合法，合法才能放入此物品；如果不放入此物品，那么就看F(Xi-1,Yj)的值是否合法，也就是是否恰好装满，如果两个都非法，本次结果就非法，若有一个合法，去合法的；都合法则取较大值。
写代码里面采用的是一个很大的负数，来避免多次判断，是的少量的加数不会是的其正，这样通过判断是负数来表示非法。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N]; // f[j]表示体积为j的情况下的总价值
int v[N], w[N]; // 物品的体积 价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
memset(f, -0x3f, sizeof f); //一开始都初始化为负无穷 方便记录是否有恰好体积为j的情况出现过
f[0] = 0; // 最开始体积为0价值为0
for(int i = 1; i <= n; i ++)
for(int j = m; j >= v[i]; j --) // j>=v[i] 保证了可以选择第i个物品
{
f[j] = max(f[j], f[j - v[i]] + w[i]); // 这里其实消去了一维
// 原式为f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
// 为了防止计算时所需要的上一层的数值被覆盖所以倒序遍历这样算f[j]时用到的f[j - v[i]]就还是和原来一样
}
int ans1 = 0, ans2 = 0;
for(int i = 0; i <= m; i ++) ans1 = max(ans1, f[i]); // 找到最大值
if(f[m] < 0) ans2 = 0; // 如果f[m]<0说明没被初始化过 没有体积恰好为m的情况出现
else ans2 = f[m]; //否则根据定义可知 f[m]的值就是背包恰好装满的情况下的最大值
cout << ans1 << endl;
cout << ans2 << endl;
}
完全背包问题
这个整体思路其实几乎就没有变，关键就在于对于物品而要，其本身就是需要两个量去表示，也就数量和种类。实际上也就是多了一个维度，但是这个维度也被背包容量限制住了。
Xi *K(K是放入物品的数量)<= Yj即可。
也就是说，我们每次在计算每个物品在每个容积的时候呢，多计算依次物品从 0-K的取值即可。
代码这里就不贴上了。可以自行取上面牛客上查看其他大佬的题解。
原文地址：https://blog.csdn.net/choose_heart/article/details/140726914
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！