P1064 [NOIP 2006 提高组] 金明的预算方案 - 洛谷

思路：

1.建立结构体：包括七个元素：主件价格，重要度，价值，附件价格，重要度，价值，附件个数；

2.输入元素部分：

（1）：总钱数n，物品个数m；

（2）：开m+1大小的数组ob，初始化为0，输入所有物品并令其从1开始编号；

（3）：判断是主件还是附件；

3.动态规划处理：

（1）：开大小为m+1的dp一维数组：dp[i]表示当前钱数为i时的最大价值；

（2）：双层for循环（正序+倒序）：第一层遍历所有物品，第二层遍历总钱数；

（3）：分类为四个情况的状态转移方程：

                情况一：有主件，无附件；

                情况二：有主件，有一个或两个附件，选择主件+第一个附件；

                情况三：有主件，有两个附件，选择主件+第二个附件；

                情况四：有主件，有两个附件，选择主件+所有附件；

详细代码：

#include <bits/stdc++.h>
using namespace std;
struct object
{
	int main_w = 0; // 主件价格
	int main_p = 0; // 主件重要度
	int main_c = 0; // 主件价值

	int se_n = 0;	   // 附件个数
	int se_w[2] = {0}; // 附件价格数组
	// 第一个元素存储第一个附件的价格
	// 第二个元素存储第二个附件的价格
	int se_p[2] = {0}; // 附件重要度数组
	// 第一格元素存储第一个附件的重要度
	// 第二个元素存储第二个附件的重要度
	int se_c[2] = {0}; // 附件价值数组
					   // 第一个元素存储第一个附件的价值
					   // 第二个元素存储第二个附件的价值
};
int main()
{
	int n = 0, m = 0;
	cin >> n >> m;
	// n：总钱数，m：物品个数
	vector<object> ob(m + 1);
	// 开m+1，物品从1开始编号
	for (int i = 1; i <= m; ++i)
	{ // 改为从1开始遍历
		int w = 0, p = 0, num = 0;
		cin >> w >> p >> num;
		// w：价格，p：重要度，num：对应主件编号
		if (num == 0)
		{ // 本身主件
			ob[i].main_w = w;
			ob[i].main_p = p;
			ob[i].main_c = w * p;
		}
		else
		{
			if (ob[num].se_n < 2) // 主件最多有2个附件
			{
				int pos = ob[num].se_n++;
				// pos：确定是第一个附件还是第二个附件
				ob[num].se_w[pos] = w;
				// 存储附件价格
				ob[num].se_p[pos] = p;
				// 存储附件重要度
				ob[num].se_c[pos] = w * p;
				// 存储附件价值
			}
		}
	}
	// 动态规划处理
	vector<int> dp(n + 1, 0); // 新增DP数组,开大小为n+1
	// 因为要从1开始计数,初始化为0
	//  dp[i]表示当钱数为i时的最大价值（钱数为i)时的状态

	for (int i = 1; i <= m; i++)
	{						  // 从第一个物品开始遍历
		int w = ob[i].main_w; // 令w值等于主件价格
		int c = ob[i].main_c; // 令c等于主件价值
		int cnt = ob[i].se_n; // 令cnt等于附件个数
		// 逆序处理预算
		for (int j = n; j >= w; j--)
		{ // 从总钱数开始遍历，直到剩下的钱数大于等于主件价格

			// 情况1：仅主件，无附件
			dp[j] = max(dp[j], dp[j - w] + c);
			// 当前最大价值等于前状态最大价值加上该主件价值
			// 两个选择：不购买当前主件
			// 或者：减去w的预算购买该主件，获得了价值c

			// 情况2：主件+附件0（即第一个附件）
			if (cnt = 1 && j >= w + ob[i].se_w[0])
			{ // 如果附件个数不为0（至少为一个），并且：剩余预算足够购买主件+附件1；
				dp[j] = max(dp[j], dp[j - w - ob[i].se_w[0]] + c + ob[i].se_c[0]);
				//-w：购买主件
				//-ob[i].se_w[0]：购买附件1
				//+c：主件价值
				//+ob[i].se_c[0]：附件1价值
			}

			// 情况3：主件+附件1（即第二个附件）
			if (cnt = 2 && j >= w + ob[i].se_w[1])
			{ // 如果附件个数不为0（为两个），并且：剩余预算足够购买主件+附件2；
				dp[j] = max(dp[j], dp[j - w - ob[i].se_w[1]] + c + ob[i].se_c[1]);
				//-w：购买主件
				//-ob[i].se_w[1]：购买附件2
				//+c：主件价值
				//+ob[i].se_c[1]：附件2价值
			}

			// 情况4：主件+双附件（两个附件都买）
			if (cnt = 2 && j >= w + ob[i].se_w[0] + ob[i].se_w[1])
			{ // 如果附件个数不为0（至少为两个），并且：剩余预算足够购买主件+附件1+附件2；
				dp[j] = max(dp[j], dp[j - w - ob[i].se_w[0] - ob[i].se_w[1]] + c + ob[i].se_c[0] + ob[i].se_c[1]);
			}
		}
	}
	cout << dp[n]; // 钱数为n的时候的最大价值
	return 0;
}