蓝桥杯算法训练VIP-装箱问题

解题思路:

注意事项:

参考代码:

Scanner scanner=new Scanner(System.in);

int v=scanner.nextInt();//容量

int n=scanner.nextInt();//物品个数

int a[]=new int[n+1];

int dp[][]=new int [n+1][v+1];

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

a[i]=scanner.nextInt();

}

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

for (int j = 1; j <=v; j++) {

if (a[i]<=j) {

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

}

else {

dp[i][j]=dp[i-1][j];

}

}

}

System.out.println(v-dp[n][v]);}