题目描述
有一个箱子容量为V(正整数0≤V≤20000)，同时有n个物品(0
要求nn个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入输出格式
输入格式：
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出格式：
1个整数，表示箱子剩余空间。
输入输出样例
输入样例#1：
24
6
8
3
12
7
9
7
输出样例#1：
0
这里先介绍最经典的动态规划
下面还有一个简化版的
import java.util.Scanner;
public class zhuangxiangwenti {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int v = sc.nextInt();
int n = sc.nextInt();
int [] num = new int [n+1];
for (int i = 1; i < num.length; i++) {
num[i]=sc.nextInt();
}
int [] [] dp = new int[n+1][v+1];
int min = Integer.MAX_VALUE;
for (int i = 1; i < n+1; i++) {
for (int j = 1; j
if(j>=num[i]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-num[i]]+num[i]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
min = Math.min(min, v-dp[i][v]);
}
System.out.println(min);
}
}
import java.util.Scanner;
public class zhuangxiangwenti2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int w = sc.nextInt();
int n = sc.nextInt();
int[] ff = new int[n];
for (int i = 0; i < ff.length; i++) {
ff[i] = sc.nextInt();
}
int[] t = new int[w + 1];
for (int i = 0; i < n; i++) {
for (int j = w; j >= 0; j--) {
if (j >= ff[i]) {
t[j] = Math.max(t[j], t[j - ff[i]] + ff[i]);
}
}
}
System.out.println(w - t[w]);
}
}