背包问题 递归&DFS 本质一样滴

背包问题

递归法（参数少，但要恢复现场）

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const int N=13;
int n=2,W=2;
int wi[N]={1,2},ci[N]={5,6};
int weight=0;
int value=0;
int ans=-1;
void b(int index)
{
	if(index==n) {if (value>ans) ans=value;
//	printf("!%d %d!",weight,value);
	return;}
	b(index+1);	//这一行也不能少 
	
	if(weight+wi[index]<=W)
	{
		weight+=wi[index];
		value+=ci[index];
		b(index+1);
		weight-=wi[index];
		value-=ci[index];//恢复现场是必要的 
	}
 
	
}
 
int main()
{
scanf("%d %d",&n,&W);
for(int i=0;i<n;i++){scanf("%d",&wi[i]);}
for(int i=0;i<n;i++){scanf("%d",&ci[i]);}
b(0);printf("%d",ans);
}

DFS（参数多，但不用回复现场） 

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const int N=13;
int n=2,W=2;
int wi[N]={1,2},ci[N]={5,6};
int weight=0;
int value=0;
int ans=-1;
void dfs(int index,int w,int c)
{
	if(index==n) 
	{
		if(ans<c) ans=c; return;
	}
	else
	{
		if(w>W) return;
		else
		{
			if(w==W){if(ans<c) ans=c;return;} 
			else
			{
		dfs(index+1,w,c);
		if(w+wi[index]<=W)//这一句不能少，之前没写，以为前面判断w<W就够了，实际是不行的，因为万一死最后一个的话会在index==n出跑掉
		dfs(index+1,w+wi[index],c+ci[index]);
				
			}
		}
	}
}

int main()
{
scanf("%d %d",&n,&W);
for(int i=0;i<n;i++){scanf("%d",&wi[i]);}
for(int i=0;i<n;i++){scanf("%d",&ci[i]);}
dfs(0,0,0);printf("%d",ans);
}

我关心的：如何保存方案？ 

在这个时候，还是用了第一种情形的恢复现场法

未经检验的代码，自测用例正确

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const int N=13;
int n=2,W=2;
int wi[N]={1,2},ci[N]={5,6};
int weight=0;
int value=0;
int ans=-1;
vector<int> temp; 
vector<int> T;
void dfs(int index,int w,int c)
{
	if(index==n) 
	{
		if(ans<c) 
		{ans=c; T=temp;return;
		}
	}
	else
	{
		if(w>W) return;
		else
		{
			if(w==W){if(ans<c) ans=c;return;} 
			else
			{
		dfs(index+1,w,c);
		temp.push_back(index);
		dfs(index+1,w+wi[index],c+ci[index]);
		temp.pop_back();
				
			}
		}
	}
}

int main()
{
scanf("%d %d",&n,&W);
for(int i=0;i<n;i++){scanf("%d",&wi[i]);}
for(int i=0;i<n;i++){scanf("%d",&ci[i]);}
dfs(0,0,0);printf("%d",ans);
for(int i=0;i<T.size();i++)printf("@%d@",T[i]);
}

·关于vector的复制（赋值），A=B之后，A不随B改变而改变

·关于vector迭代器【挖个坑】

https://blog.csdn.net/m0_68339197/article/details/139756006?spm=1001.2014.3001.5501