看似是背包,但考虑到 n 最大只有 15,DFS 枚举每个物品选或者不选即可
时间复杂度:O(215)
#include <bits/stdc++.h>
米小游是一位热爱冒险和收藏的小哥哥。最近,他迷上了购买各种精美的周边商品。不过,由于空间有限,米小游只能带一个容量为 m 的背包,背包只能装得下体积之和不超过 m 的商品。
商店里有 n 个商品,分别编号为 1 到 n,每个商品都有自己的价值 vali 和体积 wi。米小游希望在背包容量的限制下,尽可能地选择价值最高的商品。
然而,米小游面临一个难题:有些商品不能同时购买,因为它们会产生不好的化学反应。商店老板给米小游设定了 k 组互斥关系,每组关系由两个商品编号 a 和 b 组成,表示编号为 a 的商品和编号为 b 的商品不能同时购买。
米小游希望能够找到一种最佳的选择,使得他装入背包中的商品总价值最大。让我们帮米小游计算一下,如何在满足背包容量和互斥关系的情况下,获得最大价值的商品组合。
第一行输入三个整数 n,m,k,分别表示商品数量、背包容量和互斥关系数量。
接下来 n 行,每行两个整数 wi,vi,分别表示每个物品的体积和价值。
接下来 k 行,每行输入两个整数 a,b,描述一组互斥关系。
一行一个整数表示答案。
3 100 2
15 19
20 30
15 19
1 2
2 3
38
对于 100% 的数据,满足 1≤n≤15,1≤m≤109,0≤k≤15,1≤wi,vi≤109,1≤a,b≤n,a=b。