我要评论一、01背包问题
1.题目描述
01背包问题特点：每个物品只能用一次，只能选择或者不选择
2.动态规划思想
动态规划就是需要解决子问题，再通过状态转移方程拓展至整体最优。即需要满足：问题的最优解中包含的子问题也是最优的。
定义 ![f[i][j]](https://images.3wcode.com/3wcode/20240806/b_0_202408060146265056.png)
：当前背包容量为 j ，考虑前 i 个物品的最佳组合对应的价值。
当考虑背包容量为 j ，前 i 个物品的选择时，有两种想法：
① 不选择第 i 件 物品 则 ![f[i][j]=f[i-1][j]](https://images.3wcode.com/3wcode/20240806/b_0_202408060146265056.png%3df%5bi-1%5d%5bj%5d)
② 选择第 i 件 物品，则需要考虑到剩余的背包容量 j - w[ i ] ：
![f[i][j]=f[i-1][j-w[i]]+v[i]](https://images.3wcode.com/3wcode/20240806/b_0_202408060146265056.png%3df%5bi-1%5d%5bj-w%5bi%5d%5d+v%5bi%5d)
最终状态转移方程：
![j<w[i] \, \, \, \, \, \, \, \, f[i][j]=f[i-1][j]](https://images.3wcode.com/3wcode/20240806/b_0_202408060146299767.png)
、
由于状态转移过程都是由原先的状态得到的，因此思想成立。
#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;
}
二、完全背包问题
题目描述
在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.题目描述
根据多重背包与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背包的思想，即可解决问题。
发表评论