餐馆（动态规划）

灰太狼 2022-07-18 05:52 94阅读 0赞

某餐馆有n张桌子，每张桌子有一个参数：a可容纳的最大人数；有m批客人，每批客人有两个参数：b为人数，c预计消费金额。在不允许拼桌的情况下，请实现算法选择其中一部分客人，使得总预计消费金额最大。

输入包括m+2行。

第一行两个整数n（1<=n<=50000）,m(1<=m<=50000)

第二行为n个参数a，即每个桌子可容纳的最大人数，以空格分隔，范围均在32位int范围内。

接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额，以空格分隔，范围均在32位的范围内。

输出一个整数，表示最大的总预计消费金额

输入例子：

3 5

2 4 2

1 3

3 5

3 7

1 10

输入：

import java.util.*;
    
    public class Main
    
    {
    	
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		while (sc.hasNextInt()) {
    			int m = sc.nextInt();
    			int n = sc.nextInt();
    			int[] c = new int[m];
    			int[] w = new int[n];
    			for (int i = 0; i < m; i++) {
    				c[i] = sc.nextInt();
    			}
    			int[] v = new int[n];
    
    			for (int i = 0; i < n; i++) {
    				w[i] = sc.nextInt();
    				v[i] = sc.nextInt();
    			}
    
    			int[][] b = new int[n][m];
    			for (int i = 0; i < n; i++) {
    				for (int j = 0; j < m; j++) {
    					if (w[i] < c[j]) {
    						b[i][j] = v[i];
    					} else {
    						b[i][j] = 0;
    					}
    				}
    			}
    			/*
    			 * int[][] b = {
       {3,3,3}, {0,5,0}, {0,7,0}, {0,0,0}, {10,10,10}};
    			 */
    
    			int row = b.length;
    			int column = b[0].length;
    			int[][] result = new int[row][column];
    			Set<Integer> set = new HashSet<Integer>();
    			ArrayList<HashSet<Integer>> list = new ArrayList<HashSet<Integer>>();
    			for (int i = 0; i < row; i++) {
    				list.add(new HashSet<Integer>());
    			}
    			int[][] flag = new int[row][column];
    			for (int i = 0; i < row; i++) {
    				result[i][0] = b[i][0];
    				list.get(i).add(i);
    				flag[i][0] = i;
    			}
    			for (int t = 1; t < column; t++) {
    				for (int j = 0; j < row; j++) {
    					int max = 0;
    					int maxflag = 0;
    					for (int i = 0; i < row; i++) {
    						if (result[j][t - 1] + b[i][t] >= max && !list.get(j).contains(i)) {
    							max = result[j][t - 1] + b[i][t];
    							maxflag = i;
    						}
    					}
    					flag[j][t] = maxflag;
    					result[j][t] = max;
    					list.get(j).add(maxflag);
    				}
    			}
    			int rs = 0;
    			int k = 0;
    			for (int i = 0; i < row; i++) {
    				if (result[i][column - 1] > rs) {
    					rs = result[i][column - 1];
    					k = i;
    				}
    			}
    			System.out.println(rs);
    			for (int i = 0; i < column; i++) {
    				System.out.print(flag[k][i] + "-->");
    
    			}
    		}
    	}