P1725 0/1背包问题

本人的第n篇题解

这题很简单,用dfs就搞定了！

代码：

#include<iostream>
using namespace std;
int m,n,sumw,sumc,maxnc;//sumw:用来记录重量的总和,sumc:用来记录价值的总和,maxnc:用来记录最大的总和 
bool b[1000000]={0};
struct s{
	int w,c;//w表示重量,c表示价值 
} a[1000000]={0};
void dfs(int x){
	for(int i=x;i<=n;i++){
		if(sumw+a[i].w<=m&&b[i]==0){//判断sumw+这个魔法石的重量会不会超出背包重量，还要判断有没有算过 
			sumw+=a[i].w;//加上重量 
			sumc+=a[i].c;//加上价值 
			b[i]=1;//算过了 
			dfs(i);
			b[i]=0;//还原 
			sumw-=a[i].w;
			sumc-=a[i].c;
		} 
	}
	maxnc=max(sumc,maxnc);//比较最大的 
	return;
}
int main(){
	cin>>m>>n; 
	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;//输入数字 
	dfs(1);
	cout<<maxnc;//输出 
	return 0;
}

制作不易，点个赞再走吧。