题目描述：吴奶奶买鱼
吴奶奶有个可爱的外孙女——琪琪，她很喜欢小动物，尤其喜欢养鱼。为了让小孙女养到漂亮的小鱼，吴奶奶一大早就到花鸟鱼虫市场买鱼。这个市场可真大，里面有各种各样的宠物，就连宠物鱼都有好几十种。这些鱼实在是太美了，买的人越来越多，可是因为货源有限，卖鱼的老板不得不规定：同一种鱼，每个人最多只能买一条，并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。 吴奶奶想尽可能地买多些鱼，但可惜，她的资金有限，这可怎么办好呢？请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼，则选择所花资金最多的一个。
输入
输入文件的第一行为两个正整数M(M≤1000)，N(N≤30)，分别表示吴奶奶的资金和鱼的种类。以下N行，每行有两个正整数S（1≤S≤N），T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P,Q。当P,Q大于0时，表示P,Q不能共处；当P,Q均等于0时，表示输入文件的结束。
输出
文件的第一行为两个正整数X,Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中一个。
样例输入
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
样例输出
4 160
2
4
5
6 思路：就是带附加条件的背包问题，只要单独判断附加条件即可。 备注：这道写的有问题，测试用例对了，但是一直A不了。。。。。。。。。。。。。。。。。。。。
#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; const int MAX = ;
int mon, n, w[MAX], map[MAX][MAX]; struct C
{
int cost, len;
int path[MAX];
} ans; struct yu
{
int num, w;
}yyu[MAX]; int cmp(int a, int b)
{
return a < b;
} int check(int a[],int len,int inx)
{
for (int i = ; i < len; i++)
{
if (map[inx][a[i]] == )
return ;
}
return ;
} void DFS(int pos, C cur)
{
//cout << "pos:" << pos << "\tcur.len:" << cur.len << "\tcur.cost:" << cur.cost << endl; if (pos >= n + )
{
if (cur.len > ans.len && (cur.len == ans.len && cur.cost > ans.cost)) ans = cur; return;
} if (cur.cost > mon) return; if (check(cur.path,cur.len,pos))
{
C temp = cur;
temp.cost += yyu[pos].w;
temp.path[temp.len++] = yyu[pos].num;
DFS(pos + , temp);
} DFS(pos + , cur); } int main()
{
cin >> mon >> n;
for (int i = ; i <= n; i++)
cin >> yyu[i].num >> yyu[i].w; int x, y;
while (cin >> x >> y && (x||y))
{
map[x][y] = ;
map[y][x] = ;
} C t;
t.cost = ;
t.len = ;
memset(t.path, , sizeof(t.path)); DFS(, t); cout << ans.len << " " << ans.cost << endl;
sort(ans.path, ans.path + ans.len, cmp);
for (int i = ; i < ans.len; i++)
cout << ans.path[i] << endl; return ;
}
后来改过之后可以AC了。
初步猜测问题应该是：
1.多组输入。
2.鱼的编号问题，map矩阵代表鱼的标号矩阵，参数应该是鱼的编号，之前写成了索引，所以有问题。
3.初始化问题，结构体输入需要初始化。
备注：以后输入输出尽量选用同一种标准，不要一会用cincout，一会用scanfpprintf。
正确的代码：
// 吴奶奶买鱼.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h" #include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; const int MAX = ;
int mon, n, w[MAX], map[MAX][MAX]; struct C
{
int cost, len;
int path[MAX];
C()
{
cost = ;
len = ;
memset(path, , sizeof(path));
}
}ans; struct Yu
{
int num, w;
Yu()
{
num = ;
w = ;
}
}yyu[MAX]; int cmp(int a, int b)
{
return a < b;
} int check(int a[],int len,int inx)
{
for (int i = ; i < len; i++)
{
if (map[inx][a[i]] == )
return ;
}
return ;
} void DFS(int pos, C cur)
{
//cout << "pos:" << pos << "\tcur.len:" << cur.len << "\tcur.cost:" << cur.cost << endl; if (pos >= n)
{
//cout << "pos:" << pos << "\tcur.len:" << cur.len << "\tcur.cost:" << cur.cost << endl;
if ((cur.cost <= mon) && (cur.len > ans.len || (cur.len == ans.len && cur.cost > ans.cost)))
{
ans.len = cur.len;
ans.cost = cur.cost;
memcpy(ans.path, cur.path, sizeof(cur.path));
//cout << "======================pos:" << pos << "\tans.len:" << ans.len << "\tans.cost:" << ans.cost << endl;
} return;
} if (cur.cost > mon) return; if (check(cur.path,cur.len,yyu[pos].num))
{
C temp = cur;
temp.cost += yyu[pos].w;
temp.path[temp.len++] = yyu[pos].num;
DFS(pos + , temp);
} DFS(pos + , cur); } int main()
{
while (cin >> mon >> n)
{
memset(map, , sizeof(map)); for (int i = ; i < n; i++)
cin >> yyu[i].num >> yyu[i].w; int x, y;
while (cin >> x >> y && (x || y))
{
map[x][y] = ;
map[y][x] = ;
} C t;
t.cost = ;
t.len = ;
memset(t.path, , sizeof(t.path)); DFS(, t); cout << ans.len << " " << ans.cost << endl;
sort(ans.path, ans.path + ans.len, cmp);
for (int i = ; i < ans.len; i++)
cout << ans.path[i] << endl; } return ;
}