forked from damaohongtu/JavaInterview
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBeiBao_01.java
More file actions
41 lines (36 loc) · 1.12 KB
/
Copy pathBeiBao_01.java
File metadata and controls
41 lines (36 loc) · 1.12 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package BiShi;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* @Classname BeiBao_01
* @Description 有N中类型的商品,每一个有自己的体积w[i],价值v[i],容量是V,求最大的价值W
* 注意:这是一个01背包问题,每一件商品只有1个,即商品只有放入不放入的区别!
* @Date 19-6-9 下午7:34
* @Created by mao<[email protected]>
*/
public class BeiBao_01 {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while (sc.hasNext()){
int N=sc.nextInt();
//容量
int W=sc.nextInt();
//代价
int[] w=new int[N];
//价值
int[] v=new int[N];
for(int i=0;i<N;i++){
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
int[] f=new int[W+1];
for (int i=0;i<N;i++){
for(int j=W;j>=w[i];j--){
//前i个商品对应不同容器的最大价值
f[j]=Math.max(f[j],f[j-w[i]]+v[i]);
}
}
}
}
}