金明的预算方案 有依赖的背包
链接http://www.rqnoj.cn/Problem_6.html 题目描述 题目描述 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子: 输入格式 输入文件的第1行,为两个正整数,用一个空格隔开: 输出格式 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 /* 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 2200 */ 要想买一件东西,必先买其主件,形成一种依赖关系 还要注意,附件不再有从属于自己的附件,暗示了这种依赖关系只有一层,没有形成一棵树,是最简单的依赖背包
View Code
#include<stdio.h> (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |