蓝桥杯算法训练VIP-装箱问题-题解(Java代码)-01背包

import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int v=sc.nextInt();
        int n=sc.nextInt();
        int c[]=new int[n+1];
        int dp[][]=new int[n+1][v+1];
        for (int i = 1; i <= n; i++) {
            c[i]=sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <=v; j++) {
                if (j>=c[i]) {
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-c[i]]+c[i]);
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        System.out.println(v-dp[n][v]);
    }
}