CJOJ 2022 【一本通】简单的背包问题（搜索）

SYCstudio 2021-08-13 原文

CJOJ 2022 【一本通】简单的背包问题（搜索）

Description

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。

如果有满足条件的选择，则此背包有解，并输出解。（若有多组解，输出最先找到的一组解即可）

Input

第一行物品重量为s，物品的件数n
第二行每件物品的重量（输入数据均为正整数）

Output

输出物品的序号和重量

Sample Input

5 10
1 2 3 4 5

Sample Output

number:1 wieght:1
number:4 wieght:4
number:5 wieght:5

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2022

Source

递归，搜索

解决思路

简单的dfs，每次判断某个物品选或不选，注意输出顺序

不要看到背包问题就想到动归

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int maxN=5000;
const int inf=2147483647;

int n,S;
int Weight[maxN];
vector<int> Arr;

void dfs(int x,int sum);

int main()
{
	Arr.clear();
	cin>>n>>S;
	for (int i=1;i<=n;i++)
		cin>>Weight[i];
	dfs(n,0);
	cout<<"not found"<<endl;
	return 0;
}

void dfs(int x,int sum)
{
	/*cout<<x<<\' \'<<sum<<endl;
	for (int i=0;i<Arr.size();i++)
		cout<<Arr[i]<<\' \';
	cout<<endl<<endl;
	*/
	if (x==0)
		return;
	if (Weight[x]+sum<=S)
	{
		Arr.push_back(x);
		if (Weight[x]+sum==S)
		{
			for (int i=Arr.size()-1;i>=0;i--)
				printf("number:%d weight:%d\n",Arr[i],Weight[Arr[i]]);
			exit(0);
		}
		dfs(x-1,Weight[x]+sum);
		Arr.pop_back();
	}
	dfs(x-1,sum);
	return;
}