题解

看似是背包，但考虑到 $n$ 最大只有 15，DFS 枚举每个物品选或者不选即可

时间复杂度：$O(2 ^ {15})$

代码

c++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Stock {
    ll weight, value;
};

class StockSelector {
private:
    int n, m, k;
    vector<Stock> stocks;
    vector<bitset<15>> mutexes;
    ll maxValue = 0;

    bool isCompatible(int stockIndex, const bitset<15>& selected) {
        return (mutexes[stockIndex] & selected).none();
    }

    void dfs(int index, ll curValue, ll curWeight, bitset<15>& selected) {
        if (index == n) {
            maxValue = max(maxValue, curValue);
            return;
        }

        
        dfs(index + 1, curValue, curWeight, selected);


        if (isCompatible(index, selected) && curWeight + stocks[index].weight <= m) {
            selected.set(index);
            dfs(index + 1, curValue + stocks[index].value, curWeight + stocks[index].weight, selected);
            selected.reset(index);
        }
    }

public:
    void readInput() {
        cin >> n >> m >> k;
        stocks.resize(n);
        mutexes.resize(n);

        for (auto& [weight, value] : stocks) {
            cin >> weight >> value;
        }

        for (int i = 0; i < k; ++i) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            mutexes[a].set(b);
            mutexes[b].set(a);
        }
    }

    ll solve() {
        bitset<15> selected;
        dfs(0, 0, 0, selected);
        return maxValue;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    StockSelector selector;
    selector.readInput();
    cout << selector.solve() << endl;

    return 0;
}

java

import java.util.*;

public class Main {
    static long res = 0;
    static long rec = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        long m = in.nextLong();
        int k = in.nextInt();

        // 存储物品的体积和价值
        long[][] wv = new long[n + 1][2];
        for (int i = 1; i <= n; i++) {
            wv[i][0] = in.nextLong(); // 体积
            wv[i][1] = in.nextLong(); // 价值
        }

        // 处理互斥关系
        Map<Integer, Set<Integer>> conflictMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            conflictMap.put(i, new HashSet<>());
        }
        for (int i = 1; i <= k; i++) {
            int a = in.nextInt(); // 互斥物品索引从0开始
            int b = in.nextInt();
            conflictMap.get(a).add(b);
            conflictMap.get(b).add(a);
        }

        Set<Integer> ban = new HashSet<>();
        Set<Integer> used = new HashSet<>();

        dfs(1, n, m, 0, wv, conflictMap, ban, used);

        // 输出结果
        System.out.println(res);
    }

    public static void dfs (int index, int n, long m, long sumM, long[][] wv, Map<Integer, Set<Integer>> conflictMap, Set<Integer> ban, Set<Integer> used) {
        res = Math.max(res, rec);
        for (int i = index; i <= n; i++) {
            if (used.contains(i) || ban.contains(i) || sumM + wv[i][0] > m) {
                continue;
            }
            used.add(i);
            ban.addAll(conflictMap.get(i));
            sumM += wv[i][0];
            rec += wv[i][1];
            dfs(i + 1, n, m, sumM, wv, conflictMap, ban, used);
            used.remove(i);
            ban.removeAll(conflictMap.get(i));
            sumM -= wv[i][0];
            rec -= wv[i][1];
        }
    }
}

python

# n, m, k = list(map(int, input().split()))
# wList = []
# valList = []
# for _ in range(n):
#     w, val = list(map(int, input().split()))
#     wList.append(w)
#     valList.append(val)

# def insertIntoMap(k, v, exclusions):
#     if k in exclusions:
#         exclusions[k].append(v)
#     else:
#         temp = []
#         temp.append(v)
#         exclusions[k] = temp

# exclusions = {}
# for _ in range(k):
#     a, b = list(map(int, input().split()))
#     insertIntoMap(a, b, exclusions)
#     insertIntoMap(b, a, exclusions)

# def checkValid(contains, excluList):
#     for contain in contains:
#         if contain in excluList:
#             return False
#     return True

# maxVal = 0
# def dfs(contains, wtotal, valTotal, startIndex):
#     global maxVal
#     if wtotal > m:
#         return
#     elif valTotal > maxVal:
#         maxVal = valTotal
    
#     i = startIndex
#     for i in range(startIndex, n+1):
#         excluList = exclusions[i]
#         if not checkValid(contains, excluList):
#             continue
        
#         contains.append(i)
#         dfs(contains, wtotal + wList[i-1], valTotal + valList[i-1], i+1)
#         contains.pop()

# dfs([], 0, 0, 1)
# print(maxVal)
    

from collections import defaultdict

n,m,k = map(int, input().split())
stocks = []
for _ in range(n):
    a,b = map(int, input().split())
    stocks.append((a,b))

mutexs = defaultdict(set)
for _ in range(k):
    a,b = map(int, input().split())
    mutexs[a-1].add(b-1)
    mutexs[b-1].add(a-1)

def check(i,vst):
    for v in vst:
        if i in mutexs[v]:
            return False
    return True

res = 0
# 回溯枚举所有的组合
def backtrace(i,cur_value,cur_weight,vst):
    if i >= n:
        global res
        res = max(res, cur_value)
        return
    backtrace(i+1,cur_value,cur_weight,vst)
    if check(i,vst) and stocks[i][0] + cur_weight <= m:
        vst.add(i)
        backtrace(i+1, cur_value+stocks[i][1], cur_weight+stocks[i][0], vst)
        vst.remove(i)

backtrace(0,0,0,set())
print(res)

题目描述

米小游是一位热爱冒险和收藏的小哥哥。最近，他迷上了购买各种精美的周边商品。不过，由于空间有限，米小游只能带一个容量为 m 的背包，背包只能装得下体积之和不超过 m 的商品。

商店里有 n 个商品，分别编号为 1 到 n，每个商品都有自己的价值 vali 和体积 wi。米小游希望在背包容量的限制下，尽可能地选择价值最高的商品。

然而，米小游面临一个难题：有些商品不能同时购买，因为它们会产生不好的化学反应。商店老板给米小游设定了 k 组互斥关系，每组关系由两个商品编号 a 和 b 组成，表示编号为 a 的商品和编号为 b 的商品不能同时购买。

米小游希望能够找到一种最佳的选择，使得他装入背包中的商品总价值最大。让我们帮米小游计算一下，如何在满足背包容量和互斥关系的情况下，获得最大价值的商品组合。

输入格式

第一行输入三个整数 $n$，$m$，$k$，分别表示商品数量、背包容量和互斥关系数量。

接下来 $n$ 行，每行两个整数 $w_i$，$v_i$，分别表示每个物品的体积和价值。

接下来 $k$ 行，每行输入两个整数 $a$，$b$，描述一组互斥关系。

输出格式

一行一个整数表示答案。

3 100 2
15 19
20 30
15 19
1 2
2 3

38

范围

对于 $100\%$ 的数据，满足 $1\le n\le 15$，$1\le m\le 10^9$，$0\le k\le 15$，$1\le w_i,v_i\le 10^9$，$1\le a,b\le n,a\ne b$。