[NOIP2001]装箱问题

解题思路: 二维数组递归，01背包问题

注意事项:  dp[i][j]为只用前i个箱子（包含第i个）在不超过j体积下的最大利用空间

参考代码:

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

while (scanner.hasNext()) {

int V = scanner.nextInt();

int N = scanner.nextInt();

int vs[] = new int[N+1];

int dp[][]= new int[N+1][V+1];

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

            vs[i]=scanner.nextInt();

        }

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

    for(int j=1;j<=V;j++)

    if(j-vs[i]>=0)//可以放下第i个箱子

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

  else dp[i][j]=dp[i-1][j];//放不下第i个箱子

}

System.out.println(V-dp[N][V]);

}

}

}