题解 | #黄金瞳#

背包问题，话不多说看代码

import java.util.concurrent.ConcurrentHashMap;

public class Main {
        public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int i = scanner.nextInt();

        int num = scanner.nextInt();

        int[] a1 = new int[num+1];
        int[] a2 = new int[num+1];
        int[] a3 = new int[num+1];

        for (int i1 = 1; i1 < a1.length; i1++) {


            if (scanner.hasNext()) {
                a1[i1] = scanner.nextInt();
            }

        }
        for (int i1 = 1; i1 < a2.length; i1++) {
            if (scanner.hasNext()) {
                a2[i1] = scanner.nextInt();

            }
        }

        for (int i1 = 1; i1 < a3.length; i1++) {
            if (scanner.hasNext()) {
                a3[i1] = scanner.nextInt();
            }
        }

        int i1 = maxValue(i, a1, a2, a3);
        System.out.println(i1);

    }


    public static int maxValue(int a, int[] b, int[] c, int[] d)    {
        int b2=0;

        for (int i : b) {
            b2+=i;
        }

        int [] maxvalues=new int[b2+1];
        int [] c1=new int[b2+1];
        int [] d1=new int[b2+1];


        int b1=0;

        int cc=1;
        for (int i = 1; i < b.length; i++) {

            b1=b[i];

            while (b1>0){
             c1[cc]=c[i];
             d1[cc]=d[i];
                b1--;
                cc++;
            }
        }
//        int[] maxvalue = new int[b.length];
        for (int i = 0; i < maxvalues.length; i++) {
            maxvalues[i] = d1[i] - c1[i];
        }
        int [] A=new int[a+1];

        for (int i = 1; i < maxvalues.length; i++) {

            for (int j = a; j >= c1[i] ; j--) {

                A[j]=Math.max(A[j-c1[i]]+maxvalues[i],A[j]);

            }
        }

          return a+A[a];
    }
}

本质还是背包问题，动态规划， 如果将余额当成背包体积，成本当作每个物品的体积，利润即为最大价值，将各个物品最大购买数量进行求和，建立新的数组，这样就处理为背包问题了； 关于背包问题：基本思路还是 前n-1项的和与n 项的最大利润进行比较，取最大的一个。保证每一项都是最大利润； A[j]=Math.max(A[j-c1[i]]+maxvalues[i],A[j]);

图片借鉴于：https://www.bilibili.com/video/BV1K4411X766?spm_id_from=333.999.0.0