【金明的预算方案】 （C语言代码）

解题思路:

#include <stdio.h>      //基因突变版背包问题  "人人为我"递推dp  变量名都太长了···
#define max(x,y) x>y?x:y   
struct {
	int money;
	int important;
} things[61][3]={0,0};          //物品的基本信息
int main()
{
	int n,maxmoney;
	int bag[32000]={0};             //背包
	int i,j;
	int money,important,attchment;

	scanf("%d%d",&maxmoney,&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d",&money,&important,&attchment);
		if (!attchment)
		{
			things[i][0].money=money;
			things[i][0].important=important;
		}
		else
		{
			if (!things[attchment][1].money)
			{
				things[attchment][1].money=money;
				things[attchment][1].important=important;
			}
			else
			{
				things[attchment][2].money=money;
				things[attchment][2].important=important;
			}
		}
	}
	for (i=1;i<=n;i++)
	{
		if (!things[i][0].money)      //如果不是主件跳过
			continue;
		for (j=maxmoney;j>=things[i][0].money;j--)
		{
			bag[j]=max(bag[j],bag[j-things[i][0].money]+things[i][0].money*things[i][0].important);
			if (j>=things[i][0].money+things[i][1].money)
				bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][1].money]+things[i][0].money*things[i][0].important+things[i][1].money*things[i][1].important);
			if (j>=things[i][0].money+things[i][2].money)
				bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][2].money]+things[i][0].money*things[i][0].important+things[i][2].money*things[i][2].important);
			if (j>=things[i][0].money+things[i][1].money+things[i][2].money)
				bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][1].money-things[i][2].money]+things[i][0].money*things[i][0].important+things[i][1].money*things[i][1].important+things[i][2].money*things[i][2].important);
		}
	}
	printf("%d",bag[maxmoney]);
	return 0;
}

注意事项:





参考代码: