这类问题的例子：带着背包的贼闯入一家珠宝店，如果他偷的东西超过某一重量M，背包就会破裂，设每件东西都有特定的价值和重量。这个贼的两难之处在于，既要使所偷东西的总价值最大，又不能使总重量超过M。
> 01背包
01背包：n件东西的重量分别为， w[1],w[2],w[3]…w[n]，价值分别为c[1],c[2]…c[n]。设dp[w][i]代表发现第i件物品时，在总价值不超过w的前提下能带走的最大价值（即一类东西数量为1）
首先考虑情景：
不难想到，发现第i件东西时有两种情况：取两种的最大值
1. 把第i件东西放入背包：dp[i-1][W-w[i]]+c[i]（发现第i件东西前再总价值不超过W-w[i]的最大价值+第i件的价值）
如果w小于w[i]显然是不成立的，要舍弃
2. 不把第i件东西放入背包：dp[i-1][W]
为方便考虑，不妨假设第0件的价值为0，因此dp[0…][0]=0
因此可以写出方程：dp[0][..]=0;
w>=w[i]时，dp[i][w]=max(dp[i-1][w-w[i]]+c[i], dp[i-1][w])
w＜w[i]时dp[i][w]=dp[i-1][w]
代码如下：
#include<iostream>#include<algorithm>using namespace std;int main(){int N, M;cin >> N >> M;//N为总数目，M为最大重量，假设东西数目小于100，M也小于100int w[100] = {};//重量int c[100] = {};//价值int dp[100][100] = {};//已全初始化为0for (int t = 1;t <= N;t++)cin >> w[t] >> c[t];for (int i = 1;i <= N;i++)for (int W = 1;W <= M;W++)if (w[i] > W) dp[i][W] = dp[i - 1][W];elsedp[i][W] = max(dp[i - 1][W - w[i]] + c[i], dp[i - 1][W]);}
为减少空间，进行压缩
把dp[i][w]压缩成dp[w],即每次求第i组的时候对上一组（第i-1组）数据进行替换
由dp[i][w]=max(dp[i-1][w-w[i]]+c[i], dp[i-1][w]可以看出要求第i组的dp [w]需要的是第i-1组的dp[w-w[i]]+c[i]和dp[w]，即求dp[w]时需要当前的数据和w位置前的数据，因此求第i组的时候需要逆序求解，这样可以保证求dp[w]时所需的两个数据都是上一组的，而且当w＜w[i]时dp[w]=dp[w]，因此只要循环M…w[i]即可
代码如下
#include<iostream>#include<algorithm>using namespace std;int main(){int N,M;cin >> N>>M;//N为总数目，M为最大重量，假设东西数目小于100，M也小于100int w[100] = {};//重量int c[100] = {};//价值int dp[100]= {};//已全初始化为0for (int t = 1;t <= N;t++)cin >> w[t]>>c[t];for (int i = 1;i <= N;i++)for (int W =M;W>=w[i];W--)dp[W] = max(dp[W - w[i]] + c[i], dp[W]);}
> 完全背包
完全背包：每类东西的重量分别为， w[1],w[2],w[3]…w[n]，价值分别为c[1],c[2]…c[n]，并且假设没类东西的数量是无限的。设dp[w][i]代表发现第i件物品时，在总价值不超过w的前提下能带走的最大价值（即一类东西数量无限）
首先考虑情景：
不难想到，发现第i件东西时有情况：
把k个第i件东西放入背包：dp[W-k*w[i]][i-1]+k*c[i]（0<=k*w[i]<=W），取最大值
为方便考虑，不妨假设第0件的价值为0，因此dp[0][0…]=0;
因此可以写出方程：dp[0][..]=0;dp[i][W]=max(dp[W-k*w[i]][i-1]+k*c[i]（0<=k*w[i]<=W）)
可以看出要求第i组的dp [w]需要的是第i-1组的dp[i-1][W-k*w[i]]，而这个正好是dp[W-k*w[i]][i]的最优解，可以证明（若dp[i][W-k[w]]有更优解dp[i-1][W-(k+1)*w[i]]+kc[i],k!=0,此时dp[i][w]也会有更优解dp[i-1][W-(k+1)]+(k+1)*c[i]）,因此方程可以改成dp[i][W] = max(dp[i - 1][W], dp[i][W - w[i]] + c[i]);（W>w[i]时）
代码如下：
#include<iostream>#include<algorithm>using namespace std;int main(){int N, M;cin >> N >> M;//N为总数目，M为最大重量，假设东西数目小于1000，M也小于1000int w[1000] = {};//重量int c[1000] = {};//价值int dp[1000][1000] = {0};//已全初始化为0for (int t = 1;t <= N;t++)cin >> w[t] >> c[t];for (int i = 1;i <= N;i++){for (int W = 1;W <= M;W++)if (w[i] <= W)dp[i][W] = max(dp[i - 1][W], dp[i][W - w[i]] + c[i]);elsedp[i][W] = dp[i - 1][W];}cout << dp[N][M];}
同样，为减少空间，进行压缩
把dp[i][w]压缩成dp[w],即每次求第i组的时候对上一组（第i-1组）数据进行替换
由于完全背包求dp[w]时需要的是解决第i组基础上再加i物品的数据，因此求第i组的时候需要顺序求解，而且当w＜w[i]时dp[w]=dp[w]，因此只要循环w[i]…M即可
代码如下
#include<iostream>#include<algorithm>using namespace std;int main(){int N, M;cin >> N >> M;//N为总数目，M为最大重量，假设东西数目小于1000，M也小于1000int w[1000] = {};//重量int c[1000] = {};//价值int dp[1000] = {};//已全初始化为0for (int t = 1;t <= N;t++)cin >> w[t] >> c[t];for (int i = 1;i <= N;i++)for (int W = w[i];W <= M;W++)dp[W] = max(dp[W], dp[W - w[i]] + c[i]);}
多重背包
多重背包：每类东西的重量分别为， w[1],w[2],w[3]…w[n]，价值分别为c[1],c[1]…c[n]，并且假设没类东西的数量是有限的，且数量分别为d[1],d[2]…d[n]。设dp[w][i]代表发现第i件物品时，在总价值不超过w的前提下能带走的最大价值（即一类东西数量有限个）
同样先考虑情景：dp[w][i]
1.当c[i]*d[i]>=w时，可以把第i类的东西看成是无限的，即是一个完全背包问题
2.当c[i]*d[i]＜w时，可以把第i类的东西看成1个1个，即d[i]个01背包问题，当d[i]数量太多时，明显效率太低，因此可以把1个1个，看成1个，2个，4个…，2^x个，d[i]-[2^(x+1)-1]个（2^(x+2)-1>d[i]）这样对于1…d[i]的任意个数，都可由1，2，4，8…组成，即考虑了第i组，1，2，3…d[i]的每种情况，这样求出的最优解也必定是最优解，同样再对其进行压缩，按各种的情景进行求解。
代码如下
#include<iostream>#include<algorithm>using namespace std;int N, M;int dp[10000] = { 0 };//已全初始化为0void zero_one_bag(int weight,int value)//01{for (int W = M;W >=weight;W--)dp[W] = max(dp[W - weight] + value, dp[W]);}void complete_bag(int weight,int value){for (int W =weight;W <= M;W++)dp[W] = max(dp[W], dp[W - weight] + value);}int main(){int w[10000] = {};//重量int c[10000] = {};//价值int d[10000] = {};//数量cin >> N >> M;//N为总数目，M为最大重量，假设东西数目小于10000，M也小于10000for (int t = 1;t <= N;t++)cin >> w[t] >> c[t]>>d[t];for (int i = 1;i <= N;i++)if (d[i] * w[i] >= M) complete_bag(w[i], c[i]);//完全背包问题else//多个01背包问题{int t;for (t = 1;t*2-1 <= d[i];t *= 2)zero_one_bag(w[i] * t, c[i] * t);zero_one_bag(w[i] * (d[i]-t+1), c[i] * (d[i]-t+1));}}
如果觉得《背包问题之01背包 完全背包和多重背包》对你有帮助，请点赞、收藏，并留下你的观点哦！
