ACM-吴奶奶买鱼

题目描述：吴奶奶买鱼

吴奶奶有个可爱的外孙女——琪琪，她很喜欢小动物，尤其喜欢养鱼。为了让小孙女养到漂亮的小鱼，吴奶奶一大早就到花鸟鱼虫市场买鱼。这个市场可真大，里面有各种各样的宠物，就连宠物鱼都有好几十种。这些鱼实在是太美了，买的人越来越多，可是因为货源有限，卖鱼的老板不得不规定：同一种鱼，每个人最多只能买一条，并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。吴奶奶想尽可能地买多些鱼，但可惜，她的资金有限，这可怎么办好呢？请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼，则选择所花资金最多的一个。

输入

输入文件的第一行为两个正整数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行，每行有一个整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中一个。

样例输入

样例输出

4 160
2
4
5
6

思路：就是带附加条件的背包问题，只要单独判断附加条件即可。

备注：这道写的有问题，测试用例对了，但是一直A不了。。。。。。。。。。。。。。。。。。。。

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

const int MAX = 100;
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 = 0; i < len; i++)
    {
        if (map[inx][a[i]] == 1)
            return 0;
    }
    return 1;
}


void DFS(int pos, C cur)
{
    //cout << "pos:" << pos << "	cur.len:" << cur.len << "	cur.cost:" << cur.cost << endl;

    if (pos >= n + 1)
    {
        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 + 1, temp);
    }    
    
    DFS(pos + 1, cur);

}

int main()
{
    cin >> mon >> n;
    for (int i = 1; i <= n; i++)
        cin >> yyu[i].num >> yyu[i].w;

    int x, y;
    while (cin >> x >> y && (x||y))
    {        
        map[x][y] = 1;
        map[y][x] = 1;
    }
    
    C t;
    t.cost = 0;
    t.len = 0;
    memset(t.path, 0, sizeof(t.path));

    DFS(1, t);

    cout << ans.len << " " << ans.cost << endl;
    sort(ans.path, ans.path + ans.len, cmp);
    for (int i = 0; i < ans.len; i++)
        cout << ans.path[i] << endl;

    return 0;
}

后来改过之后可以AC了。

初步猜测问题应该是：

1.多组输入。

2.鱼的编号问题，map矩阵代表鱼的标号矩阵，参数应该是鱼的编号，之前写成了索引，所以有问题。

3.初始化问题，结构体输入需要初始化。

备注：以后输入输出尽量选用同一种标准，不要一会用cincout，一会用scanfpprintf。

正确的代码：

  1 // 吴奶奶买鱼.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 
  7 #include<iostream>
  8 #include <cstring>
  9 #include <cstdio>
 10 #include <algorithm>
 11 using namespace std;
 12 
 13 const int MAX = 100;
 14 int mon, n, w[MAX], map[MAX][MAX];
 15 
 16 
 17 struct C
 18 {
 19     int cost, len;
 20     int path[MAX];
 21     C()
 22     {
 23         cost = 0;
 24         len = 0;
 25         memset(path, 0, sizeof(path));
 26     }
 27 }ans;
 28 
 29 struct Yu
 30 {
 31     int num, w;
 32     Yu()
 33     {
 34         num = 0;
 35         w = 0;
 36     }
 37 }yyu[MAX];
 38 
 39 int cmp(int a, int b)
 40 {
 41     return a < b;
 42 }
 43 
 44 int check(int a[],int len,int inx)
 45 {
 46     for (int i = 0; i < len; i++)
 47     {
 48         if (map[inx][a[i]] == 1)
 49             return 0;
 50     }
 51     return 1;
 52 }
 53 
 54 
 55 void DFS(int pos, C cur)
 56 {
 57     //cout << "pos:" << pos << "	cur.len:" << cur.len << "	cur.cost:" << cur.cost << endl;
 58 
 59     if (pos >= n)
 60     {
 61         //cout << "pos:" << pos << "	cur.len:" << cur.len << "	cur.cost:" << cur.cost << endl;
 62         if ((cur.cost <= mon) && (cur.len > ans.len || (cur.len == ans.len && cur.cost > ans.cost)))
 63         {
 64             ans.len = cur.len;
 65             ans.cost = cur.cost;
 66             memcpy(ans.path, cur.path, sizeof(cur.path));
 67             //cout << "======================pos:" << pos << "	ans.len:" << ans.len << "	ans.cost:" << ans.cost << endl;
 68         }
 69         
 70         return;
 71     }
 72 
 73     if (cur.cost > mon) return;    
 74 
 75     if (check(cur.path,cur.len,yyu[pos].num))
 76     {        
 77         C temp = cur;
 78         temp.cost += yyu[pos].w;
 79         temp.path[temp.len++] = yyu[pos].num;
 80         DFS(pos + 1, temp);
 81     }    
 82     
 83     DFS(pos + 1, cur);
 84 
 85 }
 86 
 87 int main()
 88 {
 89     while (cin >> mon >> n)
 90     {        
 91         memset(map, 0, sizeof(map));
 92         
 93         for (int i = 0; i < n; i++)
 94             cin >> yyu[i].num >> yyu[i].w;
 95 
 96         int x, y;
 97         while (cin >> x >> y && (x || y))
 98         {
 99             map[x][y] = 1;
100             map[y][x] = 1;
101         }
102 
103         C t;
104         t.cost = 0;
105         t.len = 0;
106         memset(t.path, 0, sizeof(t.path));
107 
108         DFS(0, t);
109 
110         cout << ans.len << " " << ans.cost << endl;
111         sort(ans.path, ans.path + ans.len, cmp);
112         for (int i = 0; i < ans.len; i++)
113             cout << ans.path[i] << endl;
114 
115     }
116     
117 
118     return 0;
119 }