02-22 17:52 南昌航空大学 Java 发布于江西
关注
动态规划：01背包问题
import java.util.*;
public class Main {
static int []dp;
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int n= sc.nextInt();//商品个数
int V=sc.nextInt(); //背包容量
int []w=new int[n]; //物品价值
int []v=new int[n]; //物品体积
dp=new int[V+1];
for (int i = 0; i < n; i++) {
v[i]=sc.nextInt();
w[i]=sc.nextInt();
}
//先遍历物品后遍历背包,倒序遍历
for (int i = 0; i <n; i++) {
for (int j = V; j >=v[i] ; j--) {
dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
}
}
System.out.println(dp[V]);
}
}
public class Main {
static int []dp;
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int n= sc.nextInt();//商品个数
int V=sc.nextInt(); //背包容量
int []w=new int[n]; //物品价值
int []v=new int[n]; //物品体积
dp=new int[V+1];
for (int i = 0; i < n; i++) {
v[i]=sc.nextInt();
w[i]=sc.nextInt();
}
//先遍历物品后遍历背包,倒序遍历
for (int i = 0; i <n; i++) {
for (int j = V; j >=v[i] ; j--) {
dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
}
}
System.out.println(dp[V]);
}
}
全部评论
相关推荐
昨天 15:00
门头沟学院 前端工程师 点赞 评论 收藏
分享
查看12道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享