已知本厂有n个食堂，第i（i属于[1,n])个食堂有m[i]种食物， 每种食物有一个价钱c，享受度v，度度熊希望去一个食堂就餐， 花费[bot,top]范围内的钱数（也可以拍桌子走人，哪里都不吃了）， 选择若干种食物，使得自己所能获得的享受度最大。(同种食物最多选一份) 现在告诉你所有食堂食物的信息，希望你进行选择搭配，使得度度熊可以得到最大的享受度，并输出这个享受度的值。 输入描述: 第一行是三个数n，bot，top，n代表食堂数1<=n<=10），bot是这次吃饭的最低消费，top是这次吃饭的最高消费（0<=bot，top<=10000） 接下来依次是n个食堂的信息，对于第i个食堂 第一行是一个数m[i]（o<=m[i]<=100)，代表第i个食堂的食物数 第二行有2*m[i]个数，分别是c[i][1]，v[i][1]，c[i][2]，v[i][2]，……c[i][m[i]]，v[i][m[i]] c[i][j]表示第i个餐厅第j种食物的价钱，v[i][j]代表第i个餐厅第j种食物给度度熊带来的享受度。 输出描述: 对于每组数据，请输出一行，每行一个正整数。表示度度熊所能获得的最大享受度。 数据结果保证不会超过2^31-1. 输入例子: 2 10 20 5 1 1 2 1 5 1 10 1 20 1 5 1 2 2 2 5 2 10 2 20 2 输出例子: 8
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt();//食堂数 int bot=sc.nextInt();//最低消费 int top=sc.nextInt();//最高消费 int max=0; for(int i=0;i<n;i++){ int m = sc.nextInt();//食物数 int[] c = new int [m+1];//价钱 int[] v = new int [m+1];//享受度 for(int k=1;k<=m;k++){ c[k]=sc.nextInt(); v[k]=sc.nextInt(); } /* * 现有容量为top的背包 * 由于每种食物最多选一份,所以遍历一遍食物即可 * 决定要不要买一个食物,要看食物装进背包后满足感能不能提升 */ int []dp=new int[top+1]; for(int k=1;k<=m;k++){//从头开始挑食物 for(int j=top;j>=c[k];j--){//背包容量 dp[j]=Math.max(dp[j], dp[j-c[k]]+v[k]);//选能提高满足感的,所以dp[j]是最优的 } } max = Math.max(max, dp[top]); } System.out.println(max); sc.close(); } }