p1049

https://www.luogu.com.cn/problem/P1049

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int tot;
int n;
bool vis[35];
int w[35];
int minn=999999999;
//bool cmp(int x,int y){
//	return x>y?1:0;
//}
void zx(int ntot){
	//cout<<"ntot:"<<ntot<<endl;
	 if(ntot<=minn){
	 	minn=ntot;
	 }
	 for(int i=1;i<=n;i++){
	 	if(ntot-w[i]>=0 && !vis[i] && ntot-w[i]<=minn){
	 		vis[i]=1;
	 		zx(ntot-w[i]);
	 		//ntot+=w[i];
//	 		cout<<"这里回溯"<<endl;
//			cout<<"现在的ntot:"<<ntot;
//			cout<<endl<<"----"; 
	 		vis[i]=0;
		 }
	 }
}
int main(){
	memset(vis,0,sizeof(vis));
	scanf("%d",&tot);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	//sort(w+1,w+n+1,cmp);
	zx(tot);
	cout<<minn<<endl;
	return 0;
}

蒟蒻提问一下就是想要dfs如何处理背包问题的剪枝 （记忆化？）