重要的核心!!!
查看原帖
重要的核心!!!
1531031
songyuteng楼主2025/1/20 12:00

对于每件物品有4种情况可以讨论: (1)主件是否购买 (2)主件+附件1是否购买 (3)主件+附件2是否购买 (4)主件+附件1+附件2是否购买

因此状态转移方程为:

f[j] = max(f[j],f[j-主件价格]+主件价值,f[j-主件价格-附件1价格]+主件价值+附件1价值,f[j-主件价格-附件2价格]+主件价值+附件2价值,f[j-主件价格-附件1价格-附件2价格]+主件价值+附件1价值+附件2价值)

注意判断:要买的物品的价格<=j

/* 1.只要不超过N元钱就行

2.要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件

3.使每件物品的价格与重要度的乘积的总和最大 价值 = 价格 * 重要度 */

2025/1/20 12:00
加载中...