蓝桥杯算法训练VIP-装箱问题 [dp] (java代码)

解题思路:

注意事项:

参考代码:

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int v=sc.nextInt();

int n=sc.nextInt();

int[] a=new int[31];

int []dp=new int[20010];

for(int i=1;i<=n;i++) {

        a[i]=sc.nextInt();

}

for(int i=1;i<=n;i++) {

        for(int j=v;j>=1;j--) {

        if(j>=a[i]) {

        dp[j]=Math.max(dp[j], dp[j-a[i]]+a[i]);

        }

        }

}

System.out.print(v-dp[v]);

}

}