题解 | #购物单#

#include <stdio.h>
#include <stdlib.h>
#define N 60                               // 最多 60 件物品
#define M 32000                            // 最多预算数 
#define MAX(a, b) ((a) > (b)) ? (a) : (b)  // 宏函数参数最好加括号避免出错 

int main(void)
{
	int money;               // 预算
	int n;                   // 货物数量
	int v;                   // 单个物品价格
	int p;                   // 单个物品满意度
	int q;                   // 物品所属编号
	static int price[N][4];  // 存储可能的四种组合的商品的价格，静态变量自动初始化为 0 
	static int weight[N][4]; // 存储可能出现的四种组合的满意度 
	int merge_price[N][4];   // 存储合并后的价格
	int merge_weight[N][4];  // 存储合并后的满意度 
	int count = 0;           // 记录组合商品数量 
	static int dp[N][M];     // M 数量的金钱购买 N 个物品最多获取满意度
	int max = 0;             // 存储最大满意度 
	int i, j, k; 
		
	while (scanf("%d%d", &money, &n) == 2)
	{
		/* 数据处理开始，录入并合并数据*/ 
		for (i = 0; i < n; i++)
		{
			scanf("%d%d%d", &v, &p, &q);
			if (0 == q)
			{
				price[i][0] = v;
				weight[i][0] = v * p;
			}
			else if (0 == price[q - 1][1]) // 表明是数组编号为 q - 1第 1 件附件 
			{
				price[q - 1][1] = v;
				weight[q - 1][1] = v * p; 
			}
			else                           // 表明是数组编号为 q - 1的物品的第 2 件附件
			{
				price[q - 1][2] = v;
				weight[q - 1][2] = v * p;  
				price[q - 1][3] = price[q - 1][1] + v;
				weight[q - 1][3] = weight[q - 1][1] + v * p; 
			}
		}
		// 合并可能出现的商品的价格和满意度
		for (i = 0; i < n; i++)
		{
			if (price[i][0])                  // 该商品是主件 
			{
				for (j = 1; j < 4; j++)       // 只能购买包含主件的商品，合并可能购买的商品价格 
				{
					price[i][j] += price[i][0];
					weight[i][j] += weight[i][0]; 
				}
				for (j = 0; j < 4; j++)       // 剔除为 0 的数据 
				{
					merge_price[count][j] = price[i][j];
					merge_weight[count][j] = weight[i][j];
				}
				count++;
			}	
		}
		/* 数据处理完成 ，动态规划开始 */ 
		for (i = 1; i <= count; i++)                // 对于 1 ~ count 件物品 
		{
			for (j = 10; j <= money; j += 10)
			{
				max = dp[i - 1][j];                // 数量 j 的金钱购买前 i - 1 件已经出现物品最多获得满意度
				/* 开始尝试购买才出现的第 i 件物品(数组下标为 i - 1) */ 
				for (k = 0; k < 4; k++)            // 购买必须包含主件的商品之一，取最大值 
				{
					if (!merge_price[i - 1][k])    // 不存在该组合
						break; 
					if (j - merge_price[i - 1][k] >= 0) // 如果买得起某个组合，比较这笔钱 没花之前的所能购买到的最大满意度加上购买该组合新增的满意度之和 和 不购买该组合之前所得满意度的大小 
						max = MAX(max, dp[i - 1][j - merge_price[i - 1][k]] + merge_weight[i - 1][k]); // dp[i - 1] 指的是已经出现的前 i - 1 个物品的最大满意度，不是第 i 个，回退时金钱和商品编号都要减 
				}
				dp[i][j] = max;                    // 买不起或值会变小则不变，买得起且满意度增加则改变  
				/* 获得尝试购买后的最大满意度，尝试结束 */ 
			}	
		}
		printf("%d\n", dp[count][money]);
	}
	
	return 0;
}