原理:main函数的递归
将01背包代码分为4个部分,用t记录当前的状态
部分一
当t=0时,读入n和m
cin>>n>>m;
代码如下:
int main(){
......
if(t==0){
cin>>n>>m;
t=1;
main();
t=2;
main();
return 0;
}
......
}
部分二
当t=1时,读入a[]和b[]
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
可以用递归的方式进行循环,代码如下:(i初始值为1)
int main(){
......
if(t==1){
if(i>n){
t=2;
return main();
}
cin>>a[i]>>b[i];
i++;
main();
}
......
}
部分三和部分四
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[m];
当t=2时,完成外层循环的功能,特别的,在循环结束时输出结果
当t=3时,完成内层循环的功能
int main(){
if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}
完整代码如下:
#include<bits/stdc++.h>
using namespace std;
int t=0;//表示状态
int n,m,i,j;//n为物品个数,m为背包容量
int a[20005],b[20005],f[20005];//a表示代价,b表示价值
int main(){
if(t==0){
scanf("%d%d",&n,&m);
t=1;i=1;
main();
t=2;i=1;
return main();
}else if(t==1){
if(i>n){
return 0;
}
scanf("%d%d",&a[i],&b[i]);
i++;
main();
}else if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}