import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int M=sc.nextInt(); int N=sc.nextInt(); int[]dp=new int[M+1]; for (int i = 0; i < N; i++) { int w=sc.nextInt(); int v=w; int s=1; for (int j = 1; j <=s; s-=j,j*=2) { for (int k = M; k >=j*w; k--) { dp[k]=Math.max(dp[k], dp[k-j*w]+j*v); } } if(s>0){ for (int k = M; k >=s*w; k--) { dp[k]=Math.max(dp[k], dp[k-s*w]+s*v); } } } System.out.println(M-dp[M]); } }
0.0分
1 人评分