FilesExpand file tree

 master

/

Code01_Knapsack.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (57 loc) · 1.6 KB

 master

/

Code01_Knapsack.java

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (57 loc) · 1.6 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

package class19;

public class Code01_Knapsack {

// 所有的货，重量和价值，都在w和v数组里

// 为了方便，其中没有负数

// bag背包容量，不能超过这个载重

// 返回：不超重的情况下，能够得到的最大价值

public static int maxValue(int[] w, int[] v, int bag) {

if (w == null || v == null || w.length != v.length || w.length == 0) {

return 0;

}

// 尝试函数！

return process(w, v, 0, bag);

}

// index 0~N

// rest 负~bag

public static int process(int[] w, int[] v, int index, int rest) {

if (rest < 0) {

return -1;

}

if (index == w.length) {

return 0;

}

int p1 = process(w, v, index + 1, rest);

int p2 = 0;

int next = process(w, v, index + 1, rest - w[index]);

if (next != -1) {

p2 = v[index] + next;

}

return Math.max(p1, p2);

}

public static int dp(int[] w, int[] v, int bag) {

if (w == null || v == null || w.length != v.length || w.length == 0) {

return 0;

}

int N = w.length;

int[][] dp = new int[N + 1][bag + 1];

for (int index = N - 1; index >= 0; index--) {

for (int rest = 0; rest <= bag; rest++) {

int p1 = dp[index + 1][rest];

int p2 = 0;

int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];

if (next != -1) {

p2 = v[index] + next;

}

dp[index][rest] = Math.max(p1, p2);

}

}

return dp[0][bag];

}

public static void main(String[] args) {

int[] weights = { 3, 2, 4, 7, 3, 1, 7 };

int[] values = { 5, 6, 3, 19, 12, 4, 2 };

int bag = 15;

System.out.println(maxValue(weights, values, bag));

System.out.println(dp(weights, values, bag));

}

}