一、01背包问题

        1.题目描述

        有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。

        求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

         01背包问题特点：每个物品只能用一次，只能选择或者不选择

        2.动态规划思想

        动态规划就是需要解决子问题，再通过状态转移方程拓展至整体最优。即需要满足：问题的最优解中包含的子问题也是最优的。

        定义  ：当前背包容量为 j ，考虑前 i 个物品的最佳组合对应的价值。

当考虑背包容量为 j ，前 i 个物品的选择时，有两种想法：

        ① 不选择第 i 件 物品 则 

        ② 选择第 i 件 物品，则需要考虑到剩余的背包容量 j - w[ i ] ：

                                ​​​​​​​        

最终状态转移方程：

        

        、

        由于状态转移过程都是由原先的状态得到的，因此思想成立。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1010;
int f[N][N];
int v[N], w[N];
int n, m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
	f[0][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			if(j<w[i])  f[i][j]=f[i-1][j];
			if(j>=w[i]) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
		}
	cout<<f[n][m]<<endl;
	return 0;
}

         3. 01背包问题的探索

        在上述状态转移方程的过程中可以发现，在每次状态更新后，之前存储的数据不会再次用到，从而造成了空间上的浪费，可以将上述情况的二维数组压缩成一维数组，这时的数组就是动态变化的了。

        与二维数组不同的是，在第二次循环过程中，背包容量的循环量应当从大到小（m->w[i]），避免同一件物品被反复选择。 例如：

        当一件物品的体积为 1  价值为 10，当背包容量的循环量从小到大时， 运行F[1]=10，循环继续进行，F[2]=max(F[2],F[2-1]+10)=20。 即选择该物品两次，与01背包问题仅有一件商品不符，该方法适用于完全背包问题（同一件商品可以取多次）

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	for(int j=m;j>=w[i];j--)  // 从后往前，避免同一件商品反复选择（01背包）
	{
		f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
	cout<<f[m]<<endl;
	return 0;
}

二、完全背包问题

        题目描述

         有 N 件物品和一个容量是 V 的背包。每件物品数量为无限个。第 i 件物品的体积是 vi，价值是 wi。

        求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

        与01背包问题的唯一区别在于：完全背包的物品数量可以取无限个

        在01背包问题的讲述过程中已经明确解释了完全背包问题的解法：在01背包一维数组的情况下，将背包容量的循环量从小到大遍历，在数组不断更新的情况下能够让某件物品多次装入。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	for(int j=w[i];j<=m;j++)  // 从前往后，能够让某件物品多次选择（完全背包问题）
	{
		f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
	cout<<f[m]<<endl;
	return 0;
}

三、多重背包问题  

        1.题目描述

        有 N 件物品和一个容量是 V 的背包。第 i 件物品的体积是 vi，价值是 wi，数量是 ki。

        求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

        与前两种背包问题的联系：01背包和完全背包都是对于某种情况的极端，而多重背包问题则是介于二者之间，每个物品可以取不同个数的情况。

         根据多重背包与01背包，完全背包的关系，可以得出一个简单的想法：

        ①. 把多重背包问题变成01背包问题：

        即当某个物品有k个时，可以看作存在相同的体积，价值的k个不同的物品，这样就可以存在每个物品取一个或者取几个的情况。

        或者再利用一层循环 k 枚举该物品取的次数，保证存在取多次的情况。

        这种想法显然成立，但只适用于数量较少的情况，如果每种物品的数量变大，存在超时的情况，因此不是最优的解法。

       ②.联系完全背包问题

        当背包不能装在某种物品的全部数量时，即（V<w[i]*k），则此时一定不能取完，可以看作完全背包问题，此时只需要简单的讨论即可。

        将多重背包转化成01背包和完全背包的结合只能进行小优化。

        2.多重背包问题的优化

        ① 二进制优化

                例如想要取512件物品时，按照转化成01背包问题，需要从第一件枚举512件，而采用二进制的想法，把每次取物品的件数分为1，2，4，8........256.512...2^n，枚举9次就取到512件了，此外每个数都可以用二进制数的组合来表示，例如 10=1+2+4+3   15=1+2+4+8

k=1;cnt=0;
while(k<=s)    //k为枚举个数，s为物品总件数
{
	v[++cnt]=k*a;
	w[cnt]=k*b;
	s-=k;       //总物品数减去合成数
	k*=2;       //k倍增
}
if(s)// s有剩余，将剩余件数合成为新个体
{
	v[++cnt]=s*a;
	w[cnt]=s*b;
}

 将每种物品的 k 都经过上述过程，构造出两个数组（存储有二进制数的数据）价值数组和重量数组，再通过01背包的思想，即可解决问题。