动态规划之完全背包问题
状态表示f(i,j)
集合
只取前i个物品,且总体积不大于j的选择的集合(每个物品可选任意次)
属性
max
状态计算(划分集合)
物品可取0,1,2,3,4……次
划分成n个子集
状态方程$$f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])$$
朴素代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
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++) //物品可取0,1,2,3,4……次
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m]<<endl;
return 0;
}
代码优化
三维时间复杂度太大,1e9的量度,一般都会TLE
但是该状态转移方程存在一些
规律
:
1. $$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],…)$$
2. $$f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]+w[i]],f[i-1][j-3*v[i]]+2*w[i],…)$$
观察得,1式
从第二项
开始等于2式+w[i]
整理得,状态转移方程为$$f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])$$
初步优化代码
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])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
最终优化代码(滚动数组化二维为一维)
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);