消灭怪物

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n, m;
int a[N], b[N];
bool st[N];
int res = N;

void dfs(int u, int hp, int cnt)
{
	if(hp <= 0) {
		res = min(res, cnt);
		return ;
	}
	
	if(u == n + 1) return ;
	
	for(int i = 1; i <= n; i ++)
	{
		if(!st[i])
		{
			st[i] = true;
			if(hp <= b[i]) dfs(u + 1, hp - a[i] * 2, cnt + 1);
			else dfs(u + 1, hp - a[i], cnt + 1);
			st[i] = false;
		}
	}
}

int main()
{
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n >> m;
		for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
		
		res = N;
		memset(st, false, sizeof st);
		dfs(0, m, 0);

		if(res == N) puts("-1");
		else cout << res << endl;
	}

	return 0;
}

Python 状态压缩+记忆化搜索

dfs(health,m)代表剩下生命值是health，剩下技能集合是m情况下，把怪物杀死所用技能最少的数量。因为有@cache缓存状态，所以不会重复计算，很快。
初始集合u=(1<<n)-1（全1）

from math import inf
from functools import cache

def minSkill(l: list, m: int) -> int:
    n = len(l)
    u = (1 << n) - 1

    @cache
    def dfs(health: int, ss: int) -> int:
        if health <= 0:
            return 0
        if ss == 0:
            return inf

        ans = inf
        for i in range(n):
            if (ss >> i) & 1:
                A, x = l[i]
                if health <= x:
                    ans = min(ans, dfs(health - 2 * A, ss ^ (1 << i)) + 1)
                else:
                    ans = min(ans, dfs(health - A, ss ^ (1 << i)) + 1)
        return ans

    t = dfs(m, u)
    return t if t != inf else -1


T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    l = []
    for _ in range(n):
        A, x = map(int, input().split())
        l.append([A, x])
    print(minSkill(l, m))

// 暴力回溯法
#include <climits>
#include <iostream>
#include <utility>
#include <vector>
#include "bits/stdc++.h"
using namespace std;

int imin = INT_MAX;
int blood;
bool flag;
void recur(vector<pair<int, int>>& arr, int index) {
    if(index == arr.size() - 1)
    {
        // 最小技能次数
        int tmp = blood;
        int count = 0;
        for(int i = 0; i < arr.size(); i++) {
            if(tmp <= arr[i].second) {
                tmp -= arr[i].first * 2;
            }else {
                tmp -= arr[i].first;
            }
            count++;
            if(tmp <= 0) {
                flag = true;
                imin = min(count, imin);
                break;
            }
        }
    }
    for(int i = index; i < arr.size(); i++) {
        swap(arr[index], arr[i]);
        recur(arr, index+1);
        swap(arr[index], arr[i]);
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        int t1, t2;
        cin >> a >> blood;
        vector<pair<int, int>> arr;
        for (int i = 0; i < a; i++) {
            cin >> t1 >> t2;
            arr.emplace_back(make_pair(t1, t2));
        }
        flag = false;
        recur(arr, 0);

        cout << ((flag == true) ? imin : -1) << endl;
        imin = INT_MAX;
    }
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author qxm
 * @create 2023-02-27 22:12
 **/
//回溯问题的排列问题
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] jn = new int[n][2];
            for (int j = 0; j < n; j++) {
                jn[j][0] = sc.nextInt();
                jn[j][1] = sc.nextInt();
            }
            Main obj = new Main();
            obj.blood = m;
            boolean[] isUsed = new boolean[n];
            obj.backtracking(jn, isUsed);
            if (obj.min == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(obj.min);
            }
        }
    }

    int min = Integer.MAX_VALUE;
    List<Integer> path = new ArrayList<>();
    int blood = 0;

    public void backtracking(int[][] jn, boolean[] isUsed) {
        if (blood <= 0) {
            min = Math.min(min, path.size());
            return;
        }
        for (int i = 0; i < jn.length; i++) {
            if (isUsed[i]) {
                continue;
            }
            if (blood <= jn[i][1]) {
                blood -= jn[i][0] * 2;
                path.add(jn[i][0]);
                isUsed[i] = true;
                backtracking(jn, isUsed);
                isUsed[i] = false;
                path.remove(path.size() - 1);
                blood += jn[i][0] * 2;
            } else {
                blood -= jn[i][0];
                path.add(jn[i][0]);
                isUsed[i] = true;
                backtracking(jn, isUsed);
                isUsed[i] = false;
                path.remove(path.size() - 1);
                blood += jn[i][0];
            }
        }
    }
}

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();// 用例数
        int index = 0;
        while (in.hasNextInt()) {
            int skillNum = in.nextInt();
            int blood = in.nextInt();
            int[][] skills = new int[skillNum][2];
            
            for (int i = 0; i < skillNum; i++) {
                skills[i][0] = in.nextInt();
                skills[i][1] = in.nextInt();
            }
            minKilled(skills, blood);
        }
 
    }
    
    public static void minKilled(int[][] skills, int blood) {
        // skills[i] :技能伤害 小于特定值则造成双倍伤害
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < skills.length; i++) {
            boolean[] used = new boolean[skills.length];
            used[i] = true;
            ans = Math.min(ans, dfs(skills, i, blood, used, 0));
            used[i] = false;
        }
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
    
        private static int dfs(int[][] skills, int pos, int restBlood, boolean[] used, int usedSkillNum) {
        if (restBlood <= 0) {
            return 0;
        }

        if (usedSkillNum > skills.length) {
            return Integer.MAX_VALUE;
        }

        int ans = Integer.MAX_VALUE;
        int rest = restBlood - (restBlood <= skills[pos][1] ? 2 * skills[pos][0] : skills[pos][0]);
        if (rest <= 0) {
            return 1;
        }
        for (int i = 0; i < skills.length; i++) {
            if (i != pos && !used[i]) {
                used[i] = true;
                int dfs = dfs(skills, i, rest, used, usedSkillNum + 1);
                if (dfs != Integer.MAX_VALUE) {
                    ans = Math.min(ans, 1 + dfs);
                }
                used[i] = false;
            }
        }
        return ans;
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {
    public static int res;  //全局变量，可以在回溯的过程中不考虑返回值

    public static void backTracking(int[]axe, int[] cmp, int state, int m, int step) {
        if (m <= 0) {
            //血量小于0收割结果
            res = Math.min(step, res);
            return;
        }
        if (state == 0) return;
        for (int i = 0; i < axe.length; i++) {
            if (((state>>i) & 1) != 1) continue;
            int t = m - axe[i];
            if (m <= cmp[i]) t = t - axe[i]; 
            //继续向下递归
            backTracking(axe, cmp, state^(1<<i), t, step+1);
        }
        return;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            res = Integer.MAX_VALUE;
            int n = in.nextInt();
            int m = in.nextInt();
            int[] axe = new int[n];
            int[] cmp = new int[n]; 
            for (int j = 0; j < n; j++) {
                axe[j] = in.nextInt();
                cmp[j] = in.nextInt();
            } 
            int state = (1<<(n)) - 1;
            backTracking(axe, cmp, state, m, 0);
            if (res == Integer.MAX_VALUE) res = -1;
            System.out.println(res);
        }
    }
}