大虾高手都来看看帮一下忙！求解一道HOJ题目。。。 - 编程论坛

#2

诸葛修勤2011-05-12 23:41

搞个input 和 output 范例也不排列好

#3

lucky5635912011-05-13 07:56

你是没有认真看题吧?

#4

诸葛修勤2011-05-13 08:07

Sample Input
2
2 100
50 70
3 100
50 50 70

Sample Output
120
100

#5

寒风中的细雨2011-05-15 15:19

程序代码：

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

#define MSG
const int NUM = 80;

vector<unsigned int>  Goods;
bitset<NUM> bitSet;
unsigned int m, n, x;

void getInitMsg(void);
void recursion(unsigned int index, unsigned int uppound);
void deal();

int wmain(void)
{
    deal();
    return 0;
}

void getInitMsg(void)
{
#ifdef MSG
    cout << "输入商品数量: ";
#endif
    cin >> n;
#ifdef MSG
    cout << "输入优惠最低消费金额: " ;
#endif
    cin >> m;
#ifdef MSG
    cout << "输入商品的价格:";
#endif
    for (unsigned int sum=0,i=0; i<n; ++i)
    {
        cin >> x;
        sum += x;
        Goods.push_back(x);
        x = sum;
    }
}

void recursion(unsigned int index, unsigned int uppound)
{
    if (index >= uppound && uppound < n)
    {
        for (unsigned int sum=0, i=0; i<Goods.size(); ++i)
        {
            if (bitSet.test(i))
            {
                sum += Goods[i];
            }
        }
        if (sum >= m && sum <= x)
        {
            x = sum;
        }
        return;
    }
    else
    {
        bitSet.set(index);
        recursion(index+1, uppound);
        bitSet.reset(index);
        recursion(index+1, uppound);
    }
}

void deal()
{
    unsigned int i;

    getInitMsg();
    for (i=0; i<Goods.size(); ++i)
    {
        recursion(0, i);
    }

    if (x < m)
    {
        cout << "消费金额不足优惠条件" << endl;
    }
    else
    {
        cout << "最小的消费为: " << x << endl;
    }
}