题解 | #[NOIP2001]装箱问题#
[NOIP2001]装箱问题
http://www.nowcoder.com/practice/55100a6608ad4656849dbd1f16d044cb
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int V = Integer.valueOf(scan.nextLine().trim());
int n = Integer.valueOf(scan.nextLine().trim());
int[] vs = new int[n + 1];
for (int i = 1; i <= n; i++) {
vs[i] = Integer.valueOf(scan.nextLine().trim());
}
int[] dp = new int[V + 1];
for (int Goods = 1; Goods <= n; Goods++) {
for (int Volume = V; Volume >= vs[Goods]; Volume--) {
dp[Volume] = Math.max(dp[Volume], vs[Goods] + dp[Volume - vs[Goods]]);
}
}
System.out.println(V - dp[V]);
}
}
查看30道真题和解析
