ACM UVA 10306 (e-Coins)

题目： 

思路： (BFS and DP)

• BFS
  
• DP 
   When do BFS, there may be many nodes which have the same _sumConvValue and _sumInfoTechValue, so we can ignore those nodes whose _numCoin is not the smallest.

代码：

//
// UVA: 10306
// Author: xfye
// Status: AC
//
// Brief:
// BFS and DP
// When do BFS, there may be many nodes which have the same
// _sumConvValue and _sumInfoTechValue, so we can ignore those
// nodes whose _numCoin is not the smallest.
//

#include <iostream>
#include <list>

using namespace std;

#define INF 0x7fffffff

struct Node
{
    Node()
    {
        _sumConvValue = 0;
        _sumInfoTechValue = 0;
        _numCoin = 0;
    }
    int _sumConvValue;
    int _sumInfoTechValue;
    int _numCoin;
};

struct CoinType
{
    int _convValue;
    int _infoTechValue;
};

//
// g_dp[x][y]
//
// x is the sum of conventinal value
// y is the sum of InfoTech value
// g_dp[x][y] is the number of coins
//
int g_dp[310][310];
CoinType g_coinTypes[40];
int g_numCoinTypes;
int g_eModulusResult;

void search()
{
    for (int i = 0; i < 310; i++) {
        for (int j = 0; j < 310; j++) {
            g_dp[i][j] = INF;
        }
    }
    list<Node> nodeList;

    Node node;
    int minNumCoin = INF;
    nodeList.push_back(node);

    //
    // do BFS
    //
    while (nodeList.size() > 0) {
        node = nodeList.front();
        nodeList.pop_front();
        int eModulus = node._sumConvValue * node._sumConvValue + node._sumInfoTechValue * node._sumInfoTechValue;
        if (eModulus == g_eModulusResult * g_eModulusResult) {
            if (minNumCoin > node._numCoin) {
                minNumCoin = node._numCoin;
            }
        } else if (eModulus > g_eModulusResult * g_eModulusResult) {
            continue;
        }
        if (node._numCoin >= minNumCoin) {
            continue;
        }

        for (int i = 0; i < g_numCoinTypes; i++) {
            Node newNode = node;
            newNode._sumConvValue += g_coinTypes[i]._convValue;
            newNode._sumInfoTechValue += g_coinTypes[i]._infoTechValue;
            if (newNode._sumConvValue > g_eModulusResult || newNode._sumInfoTechValue > g_eModulusResult) {
                continue;
            }
            newNode._numCoin ++;
            if (g_dp[newNode._sumConvValue][newNode._sumInfoTechValue] > newNode._numCoin) {
                g_dp[newNode._sumConvValue][newNode._sumInfoTechValue] = newNode._numCoin;
                nodeList.push_back(newNode);
            }
        }
    }

    if (minNumCoin != INF) {
        cout << minNumCoin << endl;
    } else {
        cout << "not possible" << endl;
    }
}

int main()
{
    int numCases = 0;

    cin >> numCases;
    for (int i = 0; i < numCases; i++) {
        cin >> g_numCoinTypes >> g_eModulusResult;
        for (int j = 0; j < g_numCoinTypes; j++) {
            cin >> g_coinTypes[j]._convValue >> g_coinTypes[j]._infoTechValue;
        }
        search();
    }

    return 0;
}