01背包问题
朴素方法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int v[N]; // 体积
int w[N]; // 价值
int f[N][N]; // f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(j < v[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
二维优化到一维
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
{
if(j < v[i])
f[i][j] = f[i - 1][j]; // 优化前
f[j] = f[j]; // 优化后，该行自动成立，可省略。
else
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]); // 优化后
}
关于j倒序循环：首先明确二维数组状态转移f[i][]只与f[i -1][]层有关，将二维优化到一维，则一维数组要通过不断更新状态从而和二维到达等效， 而f[j] = max(f[j], f[j - v[i]] + w[i]);中j - v[i]小于j，倒序更新f[i]时f[j - v[i]是上一层未更新的状态，从而与二维数组等效。
完全背包问题
朴素方法
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1 ; i <= n ;i ++)
{
cin>>v[i]>>w[i];
}
for(int i = 1 ; i<=n ;i++)
for(int j = 0 ; j<=m ;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]);
}
cout<<f[n][m]<<endl;
}
关于状态转移方程：01背包问题状态转移方程f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);与完全背包问题状态转移方程f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);max函数中第一项f[i - 1][j]变成了f[i][j]因为要将每一层最大的f[i][j]迭代到下一层，从而找到k层中最大的f[i][j],而f[i - 1][j]不能实现迭代。
关于消k优化：
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
由上两式，可得出如下递推关系： -
f[i][j]=max(f[i-1][j],f[i][j-v]+w)
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
关于一维优化
for(int i = 1 ; i <= n ;i ++)
for(int j = 1 ; j <= m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
{
//if(j < v[i]) f[i][j] = f[i - 1][j]; //直接删去
if(j >= v[i]) f[j] = max(f[j],f[j-v[i]]+w[i]);
}
if(j < v[i]) f[i][j] = f[i - 1][j];可以直接删去，因为当j<v[i]时， f[i][j] = f[i - 1][j] 实现的是继承上一层的状态，而优化成一维后不更新f[j]则f[j]就继承了上一层的状态。
多重背包问题
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int v[N],w[N],s[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i ++) cin>>v[i]>>w[i]>>s[i];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
for(int k = 0;k <= s[i];k ++)
{
//if(j < v[i]) f[i][j] = f[i - 1][j]; //删掉
if(k*v[i] <= j) f[i][j] = max(f[i][j],f[i - 1][j - k*v[i]] + k*w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
//if(j < v[i]) f[i][j] = f[i - 1][j];这一行要删掉 不然当(j < v[i])时,k每一次循环f[i][j]被重新赋值,迭代k次找到的不一定是f[i][j]的最大值,解决方案是k从0开始循环 f[i][j]仅有一次被赋值为f[i - 1][j];
关于优化的状态方程：
多重背包
f[i,j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-sv]+sw)
f[i,j-v] = max( f[i-1,j-v], f[i-1,j-2v]+ w,...,f[i-1,j-sv]+(s-1)w,f[i-1,j-(s+1)v]+sw)
完全背包
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w ,..., f[i-1,j-k*v]+k*w )
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w ,..., f[i-1,j-(k-1)*v]+(k-1)*w )
多重背包f[i,j-v]比完全背包多了一项f[i-1,j-(s+1)v]+sw，因为完全背包没有物品个数限制，所以不管初始体积有没有减v，都会穷举到体积用完为止，所以完全背包不会多一项。
