黑马程序员技术交流社区
标题: java经典算法之背包为题（Kanpsack Problem） [打印本页]
作者: 王海彬 时间: 2015-9-17 22:21
标题: java经典算法之背包为题（Kanpsack Problem）
问题说明：
假设一个背包的负重最大可达8公斤，而希望在背包内放置负重范围内价值最高的物品。
算法代码：
1. class Fruit {
2. private String name;
3. private int size;
4. private int price;
5.
6. public Fruit(String name, int size, int price) {
7. this.name = name;
8. this.size = size;
9. this.price = price;
10. }
11.
12. public String getName() {
13. return name;
14. }
15.
16. public int getPrice() {
17. return price;
18. }
19.
20. public int getSize() {
21. return size;
22. }
23. }
24.
25. public class Knapsack {
26. public static void main(String[] args) {
27. final int MAX = 8;
28. final int MIN = 1;
29. int[] item = new int[MAX+1];
30. int[] value = newint[MAX+1];
31.
32. Fruit fruits[] = {
33. newFruit("李子", 4, 4500),
34. newFruit("苹果", 5, 5700),
35. newFruit("桔子", 2, 2250),
36. newFruit("草莓", 1, 1100),
37. newFruit("甜瓜", 6, 6700)};
38.
39. for(int i = 0; i < fruits.length;i++) {
40. for(int s =fruits.getSize(); s <= MAX; s++) {
41. int p =s - fruits.getSize();
42. intnewvalue = value[p] +
43. fruits.getPrice();
44. if(newvalue > value) {// 找到阶段最佳解
45. value = newvalue;
46. item = i;
47. }
48. }
49. }
50.
51. System.out.println("物品\t价格");
52. for(int i = MAX;
53. i >= MIN;
54. i = i -fruits[item].getSize()) {
55. System.out.println(fruits[item].getName()+
56. "\t" + fruits[item].getPrice());
57. }
58.
59. System.out.println("合计\t" + value[MAX]);
60. }
61. }
作者: 哈哈我赢了 时间: 2015-9-17 22:32
顶一个。。。。。。。
作者: Orangeapp 时间: 2015-9-17 22:39
应该附上注释会好一点，这样看不懂的人也可以根据注释去分析下。
作者: 王海彬 时间: 2015-9-17 22:43
怎么会有线。。。。。
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |