背包问题
所有的背包问题都可以归结到01背包
对于01背包化为一维使用逆序看01逆序原因
01背包只有选或不选，
完全背包可以选任意件，
多重背包最多选指定的件数
01背包
01背包只需要考虑取或者不取，所以最简单
f [ i ] [ j ]=max(f[ i-1 ] [ j ],f[ i-1 ] [ j - v [ i ] ] +w [ i ] );
前者表示不取，后者表示取
转化为一维
f[ j ] = max ( f [ j ],f [ j-v [ i ] ] + w [ i ];
完全背包
完全背包进行三次优化，从简到难，去得到更好的效率
第一种：二维方法
第二种：一维方法
第三种：在一维的基础上去掉一层循环（所选的次数占用的循环）
虽然是三种方法，但都是在二维方法上进行改动，从繁至简
题目：完全背包题目
从最复杂的也是最易懂的方法开始
#include<stdio.h>
#define X 1100
int f[X][X],v[X],w[X];
int max(int ,int );
int main(void)
{
int N,V;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=N;i++)
{
for(int j=0;j<=V;j++)
{
for(int k=0; k*v[i]<=j;k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
printf("%d\n",f[N][V]);
}
int max(int a,int b)
{
return a>b?a:b;
}
f [ i ] [ j ]=max ( f [ i ] [ j ] ,f [ i - 1 ] [ j - k * v[ i ] ]+k * w [ i ] );
用k去不断的增加件数，直到所占的体积超过要求的总体积，然后让f [ i ] [ j ]去保存最大值
#include<stdio.h>
#define X 1100
int f[X],v[X],w[X];
int max(int ,int );
int main(void)
{
int N,V;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=N;i++)
{
for(int j=0;j<V;j++)
{
for(int k=0; k*v[i]<=j;k++)
{
f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
}
}
}
printf("%d\n",f[V]);
}
int max(int a,int b)
{
return a>b?a:b;
}
删掉一个维度的原因分析
1、去掉二维的原因：对于 被去掉的一维， 所有的项只与他前一个项有关，跨项之间互不影响（i只与i-1有关），所以直接删除进行空间优化
#include<stdio.h>
#define X 1100
int f[X],v[X],w[X];
int max(int ,int );
int main(void)
{
int N,V;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=N;i++)
{
for(int j=v[i];j<=V;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d\n",f[V]);
}
int max(int a,int b)
{
return a>b?a:b;
}
//for(int j=0;j<=V;j++)
//{
// if(v[i]<=j)
// {
// f[j]=max(f[j],f[j-v[i]+w[i]]);
// }
//}
删掉k所包含的循环原因：
如果f [ j ] < f [ j-v [ i ] ]+w[ i ] 那么f[j]将会存储f[j-v[i]]+w[i]的值
然后进入下一次j循环，现在j的值已经改变成了j-v[i]，虽然后面会是j-v[i]，但实际上是j-2v[i](这里的 j 针对的是初始的 j 值 ）
多重背包
多重背包和完全背包很相似，只不过是加了一个数量限制条件
因此给完全背包的 k 循环加上限制条件就成了多重背包
如果数据的要求量比较大，三重循环就很难满足条件，很容易超时，所以需要进行优化
题目：
对数据量要求小：多重背包1
对数据量要求大：多重背包2
多重背包1
//二维做法
#include<stdio.h>
#define X 200
int f[X][X];
int w[X],v[X],s[X];
int max(int ,int );
int main(void)
{
int N,V;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&v[i],&w[i],&s[i]);
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=V;j++)
{
for(int k=0;k<=s[i] && k*v[i]<=j;k++) // 两个出口条件都要满足
{
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+k*w[i]);
}
}
}
printf("%d\n",f[N][V]);
}
int max(int a,int b)
{
return a>=b?a:b;
}
//一维做法
#include<stdio.h>
#define X 200
int f[X];
int w[X],v[X],s[X];
int max(int ,int );
int main(void)
{
int N,V;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&v[i],&w[i],&s[i]);
}
for(int i=1;i<=N;i++)
{
for(int j=V;j>=v[i];j--)
{
for(int k=0;k<=s[i] && k*v[i]<=j;k++)
{
f[j]=max(f[j],f[j-v[i]*k]+k*w[i]);
}
}
}
printf("%d\n",f[V]);
}
int max(int a,int b)
{
return a>=b?a:b;
}
如果题目对数据的要求量较大，上面的代码会超时，所以需要进行优化
在这之前必须了解的是二进制优化
因为任何一个数都可以用 2 ^ 0 到2^ n 表示，因此二进制优化是最好的方法
例如有17个价值为5的物品：我们可以把他分解成1个价值为5（1 * 5）的物品，1个价值为10的物品（2 * 5）,1个价值为20(4 * 5)的物品，1个价值为40（8 * 5）的物品，1个价值为10(2 * 5)的物品
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define X 15000
int f[X],v[X],w[X],s[X];
int max(int ,int );
int main(void)
{
int N,V;
int a,b,s;
int tot=1;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&a,&b,&s);
for(int j=1;j<s;j=j*2)
{
v[tot]=a*j;
w[tot++]=b*j;
s=s-j;
}
if(s>0)
{
v[tot]=a*s;
w[tot++]=b*s;
}
}
for(int i=1;i<=tot;i++)
{
for(int j=V;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d\n",f[V]);
}
int max(int a,int b)
{
return a>b?a:b;
}
利用二进制优化 输入数据，即使是同一价值的物品，也仍然使用不同的数据位去存储，减少循环次数
最终转化到01背包问题