求教一算法（阿里巴巴进山洞取宝）

mayongc

1。在山洞中有M件财宝,
2。价值为P1,P2.......PM
3。重两为W1,W2......WM
阿里巴巴有一个带子可放N重的物品
问1，他要那些物品时，能得到最大的价值。
   2。若有X人同行时，袋子为N1,N2 .....NX时如何得到最大价值。

只要算法，不求运算能否实现

kj501

只能穷举。

JohnBull

如果求最优解，只能穷举，比较慢。
如果求工程上的相对优解，可以利用神经网络或者遗传算法进行优选。

无双

应该是不用
好像登山法就是解这种问题的
就是如果往一条路走不通时退一步走下一条路
如果所有路都不通那么退回上一条

这样性能比较快
如果是使用穷举的话性能是很慢的

我以前贴的算法中有各种算法说明
你先看看有没有
或是上google查找

JohnBull

原帖由 "无双" 发表：
应该是不用
好像登山法就是解这种问题的
就是如果往一条路走不通时退一步走下一条路
如果所有路都不通那么退回上一条

你这不就是穷举吗？树的深度优先遍历。
因为要求的不是“如何登上山顶”，而是“如何用最短路径登上山顶”，所以不论你用深度优先还是广度优先，都必须穷举之后才能得到解。

这种发散性问题没有系统解法求最优解，只能求出相对优解。

无双

不是穷举
穷举要举所有可能

但是我的话只是说如果按一条路走
如果某一步走不通了再返回一步，
所以可能性小多了

另外这个问题在算法书中都有
到时回去看看

JohnBull

我提出一个近似解法：
计算出所有物品的价格质量比（记做c），并排序。
优先装进c较大的物品；
如果包没有装满，而因为超重无法放入任何物品时，取出最后放入的物品，把剩下的物品按P重新排序，按排序顺序寻找W最合适的物品放入即可。

JohnBull

原帖由 "无双" 发表：
不是穷举
穷举要举所有可能

但是我的话只是说如果按一条路走
如果某一步走不通了再返回一步，
所以可能性小多了

另外这个问题在算法书中都有
到时回去看看

问题是你只有穷举所有的可能才能找到最优解。利用搜索法能够更快地找到任意解，但是穷举所有解的时候不会节省时间（甚至相反）。

无双

同意
如果数量很大的话
那么要穷举时所用的时间是不可接受的

JohnBull

时间仓促，没来得及校对，简单测试了一下，似乎没问题。
权做抛砖引玉。

1. 
   
2. #include <stdio.h>;
   
3. #define jewel_count 7  /* 财宝个数 */
   
4. #define MAXWEIGHT 6  /* 最大承重 */
   
5. 
   
6. int bag[jewel_count];
   
7. int got_count=0;
   
8.         
   
9. int best_bag[jewel_count];
   
10. int best_got_count=0;
    
11. int best_value=0;
    
12.                
    
13. struct jewel_type
    
14. {      
    
15.         int p; /* Cost */
    
16.         int w; /* Weight */
    
17. };
    
18. 
    
19. struct jewel_type jewel[jewel_count];
    
20. 
    
21. void
    
22. init_hole()
    
23. {               
    
24.         int i;
    
25.         int c;
    
26.         FILE *fp;
    
27. 
    
28.         fp=fopen("/dev/urandom","r");
    
29.         for (i=0;i<jewel_count;i++) {
    
30.                 c=fgetc(fp)%5+1;  /* 重量和价值取1-5随机值 */
    
31.                 jewel[i].p=c;
    
32.                 c=fgetc(fp)%5+1;
    
33.                 jewel[i].w=c;
    
34.         }
    
35.         fclose(fp);
    
36. }
    
37. 
    
38. int
    
39. exists(int n)
    
40. {
    
41.         int i;
    
42. 
    
43.         for (i=0;i<got_count;i++) {
    
44.                 if (bag[i]==n) return 1;
    
45.         }
    
46.         return(0);
    
47. }
    
48. 
    
49. void
    
50. output()
    
51. {
    
52.         int i;
    
53.         for (i=0;i<got_count;i++) {
    
54.                 printf("%d ",bag[i]);
    
55.         }
    
56.         printf("\n");
    
57. }
    
58. 
    
59. int
    
60. weight()
    
61. {
    
62.         int i,sum=0;
    
63.         for (i=0;i<got_count;i++) {
    
64.                 sum+=jewel[bag[i]].w;
    
65.         }
    
66.         return sum;
    
67. }
    
68. 
    
69. int
    
70. value()
    
71. {
    
72.         int i,sum=0;
    
73.         for (i=0;i<got_count;i++) {
    
74.                 sum+=jewel[bag[i]].p;
    
75.         }
    
76.         return sum;
    
77. }
    
78. 
    
79. void
    
80. refresh()
    
81. {
    
82.         int i;
    
83.         if (value()>;=best_value) {
    
84.                 for (i=0;i<got_count;i++) {
    
85.                         best_bag[i]=bag[i];
    
86.                 }
    
87.                 best_got_count=got_count;
    
88.                 best_value=value();
    
89.         }
    
90. }
    
91. 
    
92. void
    
93. resolv()
    
94. {
    
95.         int i,temp;
    
96.         int tempweight;
    
97. 
    
98.         if ((tempweight=weight())<=MAXWEIGHT) {
    
99.                 refresh();
    
100.                 output();
     
101.         }
     
102.         if (tempweight>;MAXWEIGHT) {
     
103.                 return;
     
104.         }
     
105.         for (i=got_count;weight()<=MAXWEIGHT && i<jewel_count;i++) {
     
106.                 if (exists(i)==0) {
     
107.                         bag[got_count++]=i;
     
108.                         resolv();
     
109.                         got_count--;
     
110.                 }
     
111.         }
     
112. }
     
113. 
     
114. void
     
115. outputbest()
     
116. {
     
117.         int i,weight=0,value=0;
     
118. 
     
119.         printf("Best answer is:");
     
120.         for (i=0;i<best_got_count;i++) {
     
121.                 printf("%d ",best_bag[i]);
     
122.                 weight+=jewel[best_bag[i]].w;
     
123.                 value+=jewel[best_bag[i]].p;
     
124.         }
     
125.         printf("\nvalue is: %d\tweight is: %d\n",value,weight);
     
126. }
     
127. 
     
128. main()
     
129. {
     
130.         int i;
     
131.         init_hole();
     
132.         for (i=0;i<jewel_count;i++) {
     
133.                 printf("Jewel No%d: \t cost=%d \tweight=%d\n",i,jewel[i].p,jewel[i].w);
     
134.         }
     
135.         resolv();
     
136.         outputbest();
     
137. }
     
138. 
     

复制代码