/*
 *  Description: Buyer (http://noobdream.com/DreamJudge/Issue/page/1567/)
 *  Author: 鱼翔浅底
 *  Date: 2021-02-21 12:28:18
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

#define maxm 100
#define maxn 1000

typedef struct
{
    int price, weight; //价钱，受欢迎程度
} ItemList;

void Buyer(ItemList il[], int m, int n)
{
    int dp[maxm][maxn];

    memset(dp, 0, sizeof(dp));

    //dp[i][j]表示在有i钱的情况下购买前j件物品所能得到的最大欢迎度
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            //状态转移
            if (i - il[j].price >= 0 &&
                (il[j].weight + dp[i - il[j].price][j - 1] > dp[i][j - 1]))
            {
                dp[i][j] = il[j].weight + dp[i - il[j].price][j - 1];
            }
            else
            {
                dp[i][j] = dp[i][j - 1];
            }
        }
   ...