不太清楚st[u]=true;要放在这里
查看原帖
不太清楚st[u]=true;要放在这里
891384
lbming楼主2023/4/10 19:52
import java.util.*;

public class Main {

    static int N = 30;
    static int tar[] = new int[N];
    static int g[][] = new int[N][N];
    static boolean st[] = new boolean[N];
    static List<Integer> ans = new ArrayList<>();
    static int n, m, cnt;

    public static void dfs(int u, int k){
        if(u == n) return;
        if(k >= cnt) return;

        st[u] = true; // debug了一会,发现这样写能过,但是不太清楚为什么这样写

        boolean loop = true;
        for(int i = 0; i < m; i++) {
            if (tar[i] - g[u][i] > 0) {
                loop = false;
                break;
            }
        }
        if(loop){
            cnt = Math.min(cnt, k);
            ans.clear();
            for(int i = 0; i < n; i++){
                if(st[i]) ans.add(i);
            }
            return;
        }


        for(int i = 0; i < m; i++){
            tar[i] -= g[u][i];
        }
        dfs(u + 1, k + 1);
        for (int i = 0; i < m; i++){
            tar[i] += g[u][i];
        }
        st[u] = false;

        dfs(u + 1, k);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        for(int i = 0; i < m; i++) tar[i] = sc.nextInt();
        n = sc.nextInt();
        cnt = n;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                g[i][j] = sc.nextInt();
            }
        }
        dfs(0, 0);
        System.out.print(cnt + 1 + " ");
        for(int e : ans) System.out.print(e + 1 + " ");
        sc.close();
    }
}
2023/4/10 19:52
加载中...