50分求大佬看看
查看原帖
50分求大佬看看
934810
1737923221dayang楼主2023/4/3 20:49
import java.util.Scanner;

public class Main{
    static int[] need=new int[30];//需要的维生素种类和数量
    static int[][] vitami=new int[30][30];//现有的维生素总量和数量
    static int[] path=new int[30];//记录选到的维生素的序号
    static int[] endpath=new int[30];
    static int count;//表示当前已经选了多少种饲料
    static int q,v;
    static int ans=50000;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
         v=sc.nextInt();
        for(int i=1;i<=v;i++){
            need[i]=sc.nextInt();
        }
         q=sc.nextInt();
        for(int i=1;i<=q;i++){
            for(int j=1;j<=v;j++){
                vitami[i][j]=sc.nextInt();
            }
        }
        dfs(0,0);
        System.out.print(ans);
        for(int i=1;i<=ans;i++){
            System.out.print(" "+endpath[i]);
        }


    }
    static boolean check(int count){
        if(count==0) return false;
        for(int i=1;i<=q;i++){
            int sum=0;
            for(int j=1;j<=count;j++){
                sum+=vitami[path[j]][i];
            }
            if(sum<need[i]) return false;
        }
        return true;
    }
    //count 饲料总数,number 饲料编号
    static void dfs(int count,int number){
        if(number>q) return;
        if(check(count)){
            if(count<ans){
                ans=count;
                for(int i=1;i<=count;i++){
                    endpath[i]=path[i];
                }
            }
            return;
        }
        path[count+1]=number+1;
        dfs(count+1,number+1);
        path[count+1]=0;//状态恢复
        dfs(count, number+1);
    }
}
2023/4/3 20:49
加载中...