关键词：
参考（都有些错误）：
https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.md
https://blog.csdn.net/na_beginning/article/details/62884939
#include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; /* 01背包问题 每个物品仅一个 状态转移公式:F[i][j] = F[i - 1][j] 和 F[i - 1][j - W[i]] + V[i] 大的那个值 C背包总重量 W每个物品重量 V每个物品价值 n物品总数 inp具有最大价值时，标记哪个物品在包中 返回最大价值 */ int packages(int C, vector<int> &W, vector<int> &V, int n, vector<int> &inp) vector<vector<int> > F(n, vector<int>(C + 1));//F[i][j]记录背包可用重量为j时，前i个物品的最大价值 for (int i = 0; i < n; i++)//初始化表格 for (int j = 0; j < F[0].size(); j++) F[i][j] = 0; for (int j = 1; j < F[0].size(); j++)//初始化第一行 F[0][j] = (j < W[0]) ? 0 : V[0];//可用重量j大于物品重量，则装入该物品，加上该物品价值 for (int i = 1; i < n; i++) for (int j = 1; j < F[0].size(); j++) if (j < W[i]) F[i][j] = F[i - 1][j];//装不下该物品 else F[i][j] = (F[i - 1][j] < F[i - 1][j - W[i]] + V[i]) ? F[i - 1][j - W[i]] + V[i] : F[i - 1][j];//可装下该物品。状态转移方程 int result = F[n - 1][F[0].size() - 1];//最大价值 //inp标记哪些物品在包中 int j = C; for (int i = n-1; i >0 ; i--)//i不可为0，否则F[i-1]越界 if (j>W[i] && F[i][j] == F[i - 1][j - W[i]] + V[i])//注意需要j>W[i] inp[i] = 1; j -= W[i]; if (F[0][j] > 0)//如果背包还可装下，则包含第一个物品 inp[0] = 1; //输出动态规划数组 for (int i = 0; i < n; i++) for (int j = 0; j < F[0].size(); j++) cout << F[i][j] << " "; cout << endl; return result; /* 01背包问题 滚动数组优化动态规划的空间 原空间OnC，先空间O2C，但是无法输出有哪些物品在包中 */ int packages_good(int C, vector<int> &W, vector<int> &V, int n) vector<vector<int> > F(2, vector<int>(C + 1));//F[i][j]记录背包可用重量为j时，前i个物品的最大价值 for (int i = 0; i < 2; i++)//初始化表格 for (int j = 0; j < F[0].size(); j++) F[i][j] = 0; for (int j = 1; j < F[0].size(); j++)//初始化第一行 F[0][j] = (j < W[0]) ? 0 : V[0];//可用重量j大于物品重量，则装入该物品，加上该物品价值 int k = 0; for (int i = 1; i < n; i++) k = i & 1;//滚动 for (int j = 1; j < F[0].size(); j++) if (j < W[i]) F[k][j] = F[k ^ 1][j];//装不下该物品 else F[k][j] = (F[k ^ 1][j] < F[k ^ 1][j - W[i]] + V[i]) ? F[k ^ 1][j - W[i]] + V[i] : F[k ^ 1][j];//可装下该物品 return F[k][F[0].size() - 1];//最大价值 /* 完全背包 每个物品不限制数量 状态转移公式:F[i][j] = F[i - 1][j] 和 F[i][j - W[i]] + V[i] 大的那个值，标记哪些物品在包中也改变 注意是F[i][j - W[i]] + V[i] 也可优化空间 */ int packages_full(int C, vector<int> &W, vector<int> &V, int n, vector<int> &inp) vector<vector<int> > F(n, vector<int>(C + 1));//F[i][j]记录背包可用重量为j时，前i个物品的最大价值 for (int i = 0; i < n; i++)//初始化表格 for (int j = 0; j < F[0].size(); j++) F[i][j] = 0; for (int j = 1; j < F[0].size(); j++)//初始化第一行 F[0][j] = (j < W[0]) ? 0 : ((j/W[0])*V[0]);//每个物品不止一个 for (int i = 1; i < n; i++) for (int j = 1; j < F[0].size(); j++) if (j < W[i]) F[i][j] = F[i - 1][j];//装不下该物品 else F[i][j] = (F[i - 1][j] < F[i][j - W[i]] + V[i]) ? F[i][j - W[i]] + V[i] : F[i - 1][j];//可装下该物品。状态转移方程 int result = F[n - 1][F[0].size() - 1];//最大价值 //inp标记哪些物品在包中 int j = C; int i = n - 1; while (i) while(j && j > W[i] && F[i][j] <= F[i][j - W[i]] + V[i]) //如果包含该物品，则一直循环看包含几个该物品 inp[i]++; j -= W[i]; i--;//不包含该物品，则跳到下一个物品 //输出动态规划数组 for (int i = 0; i < n; i++) for (int j = 0; j < F[0].size(); j++) cout << F[i][j] << " "; cout << endl; return result; /* 多重背包 每个物品有数量限制 */ int packages_multi(int C, vector<int> &W, vector<int> &V, int n, vector<int> &inp, vector<int> &N)//N会被修改 vector<vector<int> > F(n, vector<int>(C + 1));//F[i][j]记录背包可用重量为j时，前i个物品的最大价值 for (int i = 0; i < n; i++)//初始化表格 for (int j = 0; j < F[0].size(); j++) F[i][j] = 0; for (int j = 1; j < F[0].size(); j++)//初始化第一行,每个物品有对应数量N限制 int count = (N[0] > j / W[0]) ? j / W[0] : N[0];//可用空间为j时，可以放多少个当前物品，min可放入数量,物品数量 F[0][j] = (j < W[0]) ? 0 : (count*V[0]); for (int i = 1; i < n; i++) for (int j = 1; j < F[0].size(); j++) if (j < W[i]) F[i][j] = F[i - 1][j];//装不下该物品 else int count = (N[i] > j / W[i]) ? j / W[i] : N[i]; F[i][j] = F[i - 1][j];//不放当前物品 for (int k = 1; k <= count; k++)//看放入多少个当前物品可以让F[i][j]最大 int tmp = F[i - 1][j - k * W[i]] + k * V[i];//放入k个当前物品 if (tmp > F[i][j]) F[i][j] = tmp; int result = F[n - 1][F[0].size() - 1];//最大价值 cout << result << endl; //inp标记哪些物品在包中 int j = C; int i = n - 1; while (i) while (j && N[i] && j > W[i] && F[i][j] <= F[i][j - W[i]] + V[i]) //如果包含该物品，则一直循环看包含几个该物品 inp[i]++; j -= W[i]; --N[i]; i--;//不包含该物品，则跳到下一个物品 //输出动态规划数组 for (int i = 0; i < n; i++) for (int j = 0; j < F[0].size(); j++) cout << F[i][j] << " "; cout << endl; return result; int main() vector<int> W 4,5,6,2,2 ; vector<int> V 6,4,5,3,6 ; int C = 9; int n = W.size(); vector<int> inp(n, 0);//标记是否在包中 cout << "1、01背包最大总价值：" << packages(C, W, V, n, inp) << endl; cout << "在背包中的物品编号： "; for (int i = 0; i < inp.size(); i++) if (inp[i] == 1) cout << i << " "; cout << endl; cout << "2、01背包滚动数组优化最大总价值，无法输出有哪些物品在背包中：" << packages_good(C, W, V, n) << endl; cout << endl; vector<int> inp1(n, 0);//标记是否在包中 cout << "3、完全背包最大总价值：" << packages_full(C, W, V, n, inp1) << endl; cout << "输出在背包中物品： "; for (int i = 0; i < inp1.size(); i++) cout << inp1[i] << " "; cout << endl; cout << endl; vector<int> N 1,2,2,2,4 ;//每个物品数量 vector<int> inp2(n, 0);//标记是否在包中 cout << "4、多重背包最大总价值：" << packages_multi(C, W, V, n, inp2, N) << endl; cout << "输出在背包中物品： "; for (int i = 0; i < inp2.size(); i++) cout << inp2[i] << " "; cout << endl; return 0;
01背包，完全背包，多重背包，混合背包
详见大牛背包九讲(下载地址：http://pan.baidu.com/s/1b9edXW)1//Class->物品种类，val->价值，room->所占空间，num->物品数量，Room->背包容量23#include<stdio.h>4constintmaxn=1e6;56intbag[maxn];7intRoom;89voidzero_one_bag( 查看详情
01背包完全背包多重背包
参考（都有些错误）：https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.mdhttps://blog.csdn.net/na_beginning/article/details/6 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情
01完全多重背包模板
背包问题：背包总容量为W，有n件重量为weight[i],权值为value[i]的物品1、01背包：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情
01背包+完全背包+多重背包+单调队列(代码片段)
01背包代码：逆序更新intn,m,f[105][N],dp[N];voidfun1()for(inti=1;i<=n;i++)//物品ifor(intj=1;j<=m;j++)//容量jif(j<w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1] 查看详情
acwing（基础）---01背包和完全背包多重背包问题(代码片段)
初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候... 查看详情
背包问题专栏（01，完全，多重）(代码片段)
...的模板是套用了A.S.KirigiriKyouko的模板。请dalao见谅一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和... 查看详情
动态规划多重背包问题(代码片段)
说明前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和完... 查看详情
luogu1833樱花
背包问题小合集01背包完全背包多重背包混着来对于01背包：把它想象成最大物品数为1的多重背包对于完全背包：把它想象成最大物品数为m/w[i]的多重背包对于多重背包：把它想象成。。。等等这本来就是个多重背包数据比较水... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
背包问题：0-1背包完全背包和多重背包
背包问题泛指以下这一种问题：给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。这一类问题是典型的使用动态规划解决的问... 查看详情
模板背包
（死亡）本文部分参照背包九讲（链接点这里）先看三道题：01背包，完全背包，混合背包请记住这个题面：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。有... 查看详情
背包专题c-thetroubleofxiaoqianhdu3591混合背包：多重背包+完全背包
InthecountryofALPC,Xiaoqianisaveryfamousmathematician.Sheisimmersedincalculate,andshewanttousetheminimumnumberofcoinsineveryshopping.(Thenumbersoftheshoppingincludethecoinsshegavethestoreandthestoreba 查看详情
poj3260最少硬币（01+多重+完全背包）
http://www.cnblogs.com/ACMan/archive/2012/08/14/2637437.html #include<iostream>#include<string>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath> 查看详情
混合背包（背包03）
将01背包，完全背包，和多重完全背包问题结合起来，那么就是混合三种背的问题根据三种背包的思想，那么可以得到混合三种背包的问题可以这样子求解 for(inti=1;i<=N;++i) if(第i件物品是01背包) zeroOneP... 查看详情