CJOJ 2022 【一本通】简单的背包问题（搜索）
Description
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。
如果有满足条件的选择，则此背包有解，并输出解。（若有多组解，输出最先找到的一组解即可）
第一行物品重量为s，物品的件数n 第二行每件物品的重量（输入数据均为正整数）
Output
输出物品的序号和重量
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;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7137874.html
相关资源：JAVA上百实例源码以及开源项目
