题目链接：http://acm.swust.edu.cn/problem/465/
还有一道题只是描述不一样，方法一模一样（http://acm.swust.edu.cn/problem/644/）
Time limit(ms): 1000 Memory limit(kb): 65535
Description
吴奶奶有个可爱的外孙女——琪琪，她很喜欢小动物，尤其喜欢养鱼。为了让小孙女养到漂亮的小鱼，吴奶奶一大早就到花鸟鱼虫市场买鱼。这个市场可真大，里面有各种各样的宠物，就连宠物鱼都有好几十种。这些鱼实在是太美了，买的人越来越多，可是因为货源有限，卖鱼的老板不得不规定：同一种鱼，每个人最多只能买一条，并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。
吴奶奶想尽可能地买多些鱼，但可惜，她的资金有限，这可怎么办好呢？请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼，则选择所花资金最多的一个。
吴奶奶想尽可能地买多些鱼，但可惜，她的资金有限，这可怎么办好呢？请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼，则选择所花资金最多的一个。
Input
输入文件的第一行为两个正整数M(M≤1000)，N(N≤30)，分别表示吴奶奶的资金和鱼的种类。以下N行，每行有两个正整数S（1≤S≤N），T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P,Q。当P,Q大于0时，表示P,Q不能共处；当P,Q均等于0时，表示输入文件的结束。
接着，每行有两个整数P,Q。当P,Q大于0时，表示P,Q不能共处；当P,Q均等于0时，表示输入文件的结束。
Output
文件的第一行为两个正整数X,Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中一个。
如果题目有多个解，只需输出其中一个。
Sample Input
|
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
|
Sample Output
|
4 160
2
4
5
6
|
Hint
解题思路：这道题除去鱼之间的相互吞食，和输出所购买的鱼，就是一个0-1背包问题。
现在在0-1背包的基础上为了达到以上两点设计一个dfs算法，递归模拟这个过程，在代码中有详细的注释，这里就不多说了~~~
代码如下：
/******************0-1背包+dfs******************/
#include <iostream>
using namespace std; #define rep(i,a,b) for(int i=a;i<=b;i++) int buy[], sign[];//sign标记鱼的购买状态,buy最优购买方案
int mpt[][];//表示鱼的相互克制状态
int val, num, n, m, vi[];//vi价格 void dfs(int cur, int sum, int cnt){
int ptr[];//中转变量
if (cur > n){
if (num<cnt || (num == cnt&&sum>val)){
num = cnt;
val = sum;
rep(i, , n)buy[i] = sign[i];
}
return;
}
if (!sign[cur] && sum + vi[cur] <= m){
rep(i, , n) ptr[i] = sign[i];
sign[cur] = ;//标记这条鱼已购买
rep(i, , n){
if (mpt[cur][i] && !sign[i])
sign[i] = ;
}
dfs(cur + , sum + vi[cur], cnt + );
//还原鱼的购买状态，方便下一次搜索
rep(i, , n) sign[i] = ptr[i];
sign[cur] = ;
}
dfs(cur + , sum, cnt);
}
int main(){
int a, b;
cin >> m >> n;
//鱼不一定按顺序给出,坑爹啊~~
rep(i, , n){
cin >> a;
cin >> vi[a];
}
cin >> a >> b;
while (a || b){
mpt[a][b] = mpt[b][a] = ;
cin >> a >> b;
}
dfs(, , );
cout << num << ' ' << val <<endl;
rep(i, , n){
if (buy[i] == )
cout << i << endl;
}
return ;
}