华为OD机试2023真题- 贪心的商人 给出Java代码
时间: 2023-10-31 20:04:49 浏览: 76
题目描述:
有一个商人手中有n个物品,每个物品有一个重量和一个价值,他希望从中选择总重量不超过W的物品,使得选择的物品价值总和最大。
输入格式:
第一行包含整数n和W,表示物品数量和背包容量。
接下来n行,每行包含两个整数w和v,表示一个物品的重量和价值。
输出格式:
输出一个整数,表示可获得的最大价值。
数据范围:
1≤n≤1000,
1≤W≤1000,
1≤w≤1000,
1≤v≤1000
样例:
输入:
4 5
1 2
2 4
3 4
4 5
输出:
8
Java代码实现:
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int W = sc.nextInt();
int[] w = new int[n+1];
int[] v = new int[n+1];
for(int i=1;i<=n;i++){
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
int[] f = new int[W+1];
for(int i=1;i<=n;i++){
for(int j=W;j>=w[i];j--){
f[j] = Math.max(f[j],f[j-w[i]]+v[i]);
}
}
System.out.println(f[W]);
}
}