1维完全背包
题目链接:Acwing
朴素解法
dfs
状态与状态值
$f[i][j] = 用前i个物品拼出重量小于等于j的方案中,最大价值【注意,不是等于j】$
转移方程
$f[i][j] = \max\limits_{k>=0}\left\{f[i-1][j-k S_{i}]+k P_{i}\right\}$
边界与初始值
$f[0][j] = 0$
Tip
会$TLE$
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int dfs(int i, int j){ //用前i个物品拼出重量小于等于j的方案中,最大价值【注意,不是等于j】
if(i==0) return 0; //base case
int res = dfs(i-1, j);
for(int k=1; j-k*s[i]>=0; k++){
res = max( res, dfs(i-1, j-k*s[i])+k*p[i] );
}
return res;
}
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
cout<<dfs(n, c);
return 0;
}
时间优化1:空间换时间
以下的时间优化基于两个父问题的子问题有重叠,所以在计算出子问题解后记录下来,避免重复计算
dfs+memo
仍然$TLE$
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[N][N];
int dfs(int i, int j){ //边算边存
if(f[i][j]!= -1) return f[i][j];
if(i==0) return f[i][j] = 0; //base case
int res = dfs(i-1, j);
for(int k=1; j-k*s[i]>=0; k++){
res = max( res, dfs(i-1, j-k*s[i])+k*p[i] );
}
return f[i][j] = res;
}
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
memset(f, -1, sizeof f);
cout<<dfs(n, c);
return 0;
}
递推+dpTable
仍然$TLE$
#include<iostream>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[N][N];
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
for(int i=0; i<=n; i++){
for(int j=0; j<=c; j++){
if(i==0){ f[i][j]=0; continue;} //base case
f[i][j] = f[i-1][j];
for(int k=1; j-k*s[i]>=0; k++){
f[i][j] = max( f[i][j], f[i-1][j-k*s[i]]+k*p[i] );
}
}
}
cout<<f[n][c];
return 0;
}
时间优化2:利用内蕴规律(信息)
空间换时间的优化用尽,但仍然不够
以下的优化基于:同阶段的两个父问题,其子问题重叠度太高,以至于在父问题可以直接利用另一个父问题的解
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-3×v]+2×w , .....)
由上两式,可得出如下递推关系: f[i][j]=max(f[i,j-v]+w , f[i-1][j])
内蕴规律的发现,需要一些数学直觉,并没有固定的方法论
dfs+memo+内蕴规律
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[N][N];
int dfs(int i, int j){ //边算边存
if(f[i][j]!= -1) return f[i][j];
if(i==0) return f[i][j] = 0; //base case
int res = dfs(i-1, j);
if(j-s[i]>=0) res = max(res, dfs(i, j-s[i])+p[i]);
return f[i][j] = res;
}
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
memset(f, -1, sizeof f);
cout<<dfs(n, c);
return 0;
}
递推+dpTable+内蕴规律
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[N][N];
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
for(int i=0; i<=n; i++){
for(int j=0; j<=c; j++){
if(i==0){ f[i][j]=0; continue;} //base case
f[i][j]=f[i-1][j];
if(j-s[i]>=0) f[i][j]=max(f[i][j], f[i][j-s[i]]+p[i]);
}
}
cout<<f[n][c];
return 0;
}
空间优化
滚动数组
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[2][N];
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
int old, now=1;
for(int i=0; i<=n; i++){
old = now, now = 1-old;
for(int j=0; j<=c; j++){
if(i==0){ f[now][j]=0; continue;} //base case
f[now][j]=f[old][j];
if(j-s[i]>=0) f[now][j]=max(f[now][j], f[now][j-s[i]]+p[i]);
}
}
cout<<f[now][c];
return 0;
}
状态压缩
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N], p[N];
int f[N];
int main(){
int n, c; //c: capacity
cin>>n>>c;
for(int i=1; i<=n; i++){
cin>>s[i]>>p[i];
}
for(int i=0; i<=n; i++){
for(int j=0; j<=c; j++){
if(i==0){ f[j]=0; continue;} //base case
if(j-s[i]>=0) f[j]=max(f[j], f[j-s[i]]+p[i]);
}
}
cout<<f[c];
return 0;
}