4
#yyds干货盘点# 动态规划专题：装箱问题
source link: https://blog.51cto.com/u_15488507/5884297
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：装箱问题
精选 原创1.简述：
描述
有一个箱子容量为 V ，同时有n个物品，每个物品有一个体积（正整数）。每个物品只能使用一次。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
数据范围： ，
，每个物品的体积满足
输入描述：
第一行输入一个正整数 V 表示箱子的容量，
第二行输入一个正整数 n 表示物品的个数。
后续 n 行每行输入一个正整数表示物品的体积
输出描述：
输出箱子最小剩余空间
示例1
24
6
8
3
12
7
9
7
6
8
3
12
7
9
7
2.代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int V=in.nextInt();
int n=in.nextInt();
int[] nums=new int[n];
for(int i=0;i<n;i++) nums[i]=in.nextInt();
boolean[] dp=new boolean[V+1];
dp[0]=true;
for(int i=0;i<n;i++){
for(int j=V;j>=nums[i];j--){
dp[j]=dp[j]|dp[j-nums[i]];
}
}
for(int i=V;i>=0;i--){
if(dp[i]){
System.out.println(V-i);
return;
}
}
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int V=in.nextInt();
int n=in.nextInt();
int[] nums=new int[n];
for(int i=0;i<n;i++) nums[i]=in.nextInt();
boolean[] dp=new boolean[V+1];
dp[0]=true;
for(int i=0;i<n;i++){
for(int j=V;j>=nums[i];j--){
dp[j]=dp[j]|dp[j-nums[i]];
}
}
for(int i=V;i>=0;i--){
if(dp[i]){
System.out.println(V-i);
return;
}
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK