题解 | #购物单#

#include <stdio.h>
#include <string.h>
#define MAX(a,b) ((a>b)?(a):(b))

int main(void)
{
    int N = 0, m = 0;
    scanf("%d %d",&N, &m);
    N /= 10;//10的倍数，减少后续循环次数
    /*  每个物品的选择有4种组合：
        1、只选主件；
        2、选主件+附件1；
        3、选主件+附件2；
        4、选主件+附件1+附件2；
     */
    int price[m][4];//4种组合下的 价格
    int value[m][4];//4种组合下的 价格 * 重要度 = 价值
    memset(price, 0, sizeof(price));//置0，方便判断
    memset(value, 0, sizeof(value));//置0，方便判断

    /* 将主件、附件的价格和价值，添加到价格和价值数组中 */
    int v,p,q;
    for(int i = 0 ; i < m ; i++)
    {
        scanf("%d %d %d",&v, &p, &q);
        v /= 10;//10的倍数，减少后续循环次数
        /* 主件 */
        if(q == 0)
        {
            price[i][0] = v;
            value[i][0] = v * p;
        }
        /* 附件1 */
        else if(price[q - 1][1] == 0)
        {
            price[q - 1][1] = v;
            value[q - 1][1] = v * p;
        }
        else
        {
            /* 附件2 */
            price[q - 1][2] = v;
            value[q - 1][2] = v * p;

            /* 附件1 + 附件2 */
            price[q - 1][3] = price[q - 1][1] + price[q - 1][2];
            value[q - 1][3] = value[q - 1][1] + value[q - 1][2];
        }
    }
    /* 将主件的价格和价值，添加到附件的组合中 */
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 1 ; j < 4 ; j++)
        {
            price[i][j] += price[i][0];
            value[i][j] += value[i][0];
        }
    }

    int dp[m + 1][N + 1];//数组的值表示：用N(j)奖金购买前m(i)个物品的总价值
    memset(dp, 0, sizeof(dp));//初始化为0
    /*  
        dp[m + 1][N + 1]说明：

        在不放任何物品的情况下，初值为 dp[0][j] = 0，然后根据初值进行递推dp[1][j]，dp[2][j]等等；
        首先我们对物品i只有两种处理结果：拿或是不拿；
        1）如果拿物品i：
            那么奖金就将减少，价值也将增加，放入i后的价值：dp[i-1][j-price[i]] + value[i]。
            为什么是dp[i-1]？因为在决定第i个物品时，必须参考前i个物品的最优选择；正因为如此，得到的结果总是最优解。
        2）如果不拿物品i：
            那么奖金不变，价值不变，等于前i-1个物品的价值：dp[i-1][j]
        因此，公式可以总结为：dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-price[i]] + value[i])，其中j-price[i]满足 >= 0

    */
   int max_value = 0;
    for(int i = 1 ; i < m + 1 ; i++)//m件物品
    {
        for(int j = 1 ; j < N + 1 ; j++)//总金额递减
        {
            max_value = dp[i-1][j];//先默认价值最大值为前i件物品的价值
            for(int k = 0 ; k < 4 ; k++)//每件物品有4中组合购买方式
            {
                if(k > 0 && price[i-1][k] == price[i-1][0])//说明该物品没有附件
                {
                    break;
                }
                if(j - price[i-1][k] >= 0)//剩余奖金足够购买当前物品时
                {
                    /* 公式，当前价值最大值与添加当前物品后的价值进行比较，择优选择*/
                    max_value = MAX(max_value, dp[i-1][j - price[i-1][k]] + value[i-1][k]);
                }
            }
            dp[i][j] = max_value;
        }
   }
    printf("%d\r\n", dp[m][N] * 10);//之前的价格和奖金都除以10，因此最后要乘上10
}