Swust oj 195: buyer

    截止2020/6/23,oj还是没更新c++11标准,所以这个没法通过编译,解决:

std::vector<std::pair<int, int>> 改为std::vector< std::pair<int, int> >
auto不能用
rbegin替换为end,然后迭代器自减即可

    源码:

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

//动规数组
int form[1000][1000];

//寻找收益的最大值
int FindMaxValue(std::vector<std::pair<int, int>> foodArray, int money, int amount);
/* 第一个参数是食物数组,第二个参数是钱总数,第三个参数是食物总数*/

//按字典序查找路径
std::vector<int> FindMaxPath(std::vector<std::pair<int, int>> foodArray, int money, int amount);
/* 第一个参数是食物数组,第二个参数是钱总数,第三个参数是食物总数*/

int main()
{
    int money, amount;

    while (std::cin >> money >> amount)
    {
        //食物数组
        std::vector<std::pair<int, int>> foodArray;
        /* 第一个参数是价格,第二个参数是收益 */

        //动规数组初始化
        memset(form, 0, sizeof(form));

        //价格的中间变量
        int mid_price(0), mid_income(0);
        /* 用于数组输入 */

        for (int i(0); i < amount; ++i)
        {
            std::cin >> mid_price >> mid_income;
            foodArray.push_back(std::make_pair(mid_price, mid_income));
        }

        //寻找收益最大值
        int maxValue = FindMaxValue(foodArray, money, amount);

        //寻找物品
        std::vector<int> path = FindMaxPath(foodArray, money, amount);

        //结果输出:反向输出rbegin
        std::cout << maxValue << std::endl;
        for (auto it = path.rbegin(); it != path.rend(); ++it)
        {
            std::cout << *it;

            //判断是否需要换行
            if (it == path.rend())
            {
                std::cout << std::endl;
            }
            else if (it != path.rend())
            {
                std::cout << ' ';
            }
        }

    }
}

//寻找收益的最大值
int FindMaxValue(std::vector<std::pair<int, int>> foodArray, int money, int amount)
{
    for (int i(0); i < money; ++i)
    {
        if (foodArray[0].first > i + 1)                     //如果第0个物品价格 大于总钱数i
        {
            form[0][i] = 0;
        }
        else if (foodArray[0].first <= i + 1)
        {
            form[0][i] = foodArray[0].second;
        }
    }

    for (int i(0); i < amount; ++i)
    {
        for (int j(0); j < money; ++j)                      //j+1:当前的钱
        {
            if (j + 1 - foodArray[i].first < 0)             //当前的钱买不起第i个物品
            {
                form[i][j] = form[i - 1][j];
            }
            else if (j + 1 - foodArray[i].first >= 0)       //当前的钱买得起第i个物品
            {
                form[i][j] = std::max(form[i - 1][j], (foodArray[i].second + form[i - 1][(j - foodArray[i].first)]));
            }
        }
    }

    return form[amount - 1][money - 1];
}

std::vector<int> FindMaxPath(std::vector<std::pair<int, int>> foodArray, int money, int amount)
{
    std::vector<int> re;

    --money;
    --amount;

    while (amount > -1)  //amount最小值可以为0
    {
        if (form[amount][money] > form[amount - 1][money])
        {
            re.push_back((amount + 1));
            money -= foodArray[amount].first;
        }
        --amount;
    }

    return re;
}