题解 | #购物单#

#include <stdio.h>
#include <string.h>
//动态规划 f(n) =Q [f(n-1) f(n-2)..]
//新的优化结果可以由过去的结果结合确定的策略得到
//0-1背包问题 包称重W   物品W(i) V(i)
//dp[3][4] 表示 3个物品 重量为4 时规划得到的最大值
//dp[i][j] = max dp[i-1][j] 物品i不放进背包, dp[i-1][j-w[i]]+v(i) 物品i放进背包
//本题30个物品  price  price*import
//划分 以主件为入背包的i
//无附件主件   dp[i][j] = max 物品i不放进背包 物品i放进背包
//有附件主件   dp[i][j] = max 物品i不放进背包 物品i放进背包 物品i+附件1进背包 物品i+附件2 i+附件1and2
//更新price[i][k] k 0-3 标识 主件 主+附件1 主+附件2 主+附件12 的 price he price*import   之后用j>w[i][k] 判断
//经验教训  1.初始化数组在定义时不行的话 就用一个双循环 不要在具体流程中进行初始化会乱
//2.对不同的系统变量就设置不同的状态标识 比如题目 总商品数和 主件数量就是不同的
//3.c = a>b ? a:b;  <=> max
//4.0-1背包dp在对f(n) = max(1,2,3,4) (1234是n-1函数)时 可以令fn = 1,然后for遍历234 根据当前承重与物品重量比较判断是否进入对2,3,4的比较 
typedef struct productinfo
{
	int price;
	int import;
	int q;
} productinfo;

int max(int a, int b);

int main()
{
	//读入数据
	int N, m;
	scanf("%d %d", &N, &m);
	int i, j;
	productinfo product[m + 1];
	int w[m + 1][4], v[m + 1][4], mainnum = 0;
	for (i = 0; i < m + 1; i++)
		for (j = 0; j < 4; j++)
			w[i][j] = 0, v[i][j] = 0;

	int t;
	for (i = 1; i <= m; i++)
	{

		scanf("%d %d %d", &product[i].price, &product[i].import, &product[i].q);
		//负载  价值表
		if (product[i].q == 0)
		{
			w[i][0] = w[i][1] = w[i][2] = w[i][3] += product[i].price;
			v[i][0] = v[i][1] = v[i][2] = v[i][3] += product[i].import * product[i].price;
			mainnum++;
		}
		else
		{
			t = product[i].q;
			if (w[t][0] == w[t][1])
				w[t][1] += product[i].price;
			else
				w[t][2] += product[i].price;

			w[t][3] += product[i].price;

			if (v[t][0] == v[t][1])
				v[t][1] += product[i].import * product[i].price;
			else
				v[t][2] += product[i].import * product[i].price;

			v[t][3] += product[i].import * product[i].price;
		}
	}

	//带附件的负载价值表

	//dp i j  到第i个主件 在N下的最大值
	//主件编号 1-30  1-mainnum
	//数组0 1-mainbun  0 1 N/10
	int dp[mainnum + 1][N / 10 + 1];
	int count = 0;

	for (i = 0; i < mainnum + 1; i++)
		for (j = 0; j < N / 10 + 1; j++)
			dp[i][j] = 0;

	for (i = 1; count <= mainnum && i <= m; i++)
	{
		if (w[i][0] + v[i][0] != 0)
		{
			count++;
			//录入一个主件
			for (j = 0; j <= N / 10; j++)
			{

				dp[count][j] = dp[count - 1][j];
				for (int k = 0; k < 4; k++)
				{
					if (j * 10 >= w[i][k])
						dp[count][j] = max(dp[count][j], dp[count - 1][j - w[i][k] / 10] + v[i][k]);
				}
			}
		}
	}

	printf("%d", dp[mainnum][N / 10]);

	return 0;
}

int max(int a, int b)
{
	int max = a;
	if (b > max)
		max = b;
	return max;
}