01背包问题如何求得最佳取法，而不仅是最大价值。

cobras

发个背包问题贪心算法与动态规划比较。少数情况下贪心算法不能求最佳答案。

1. /* knapsack.c */
   
2. 
   
3. #include <stdlib.h>
   
4. #include <stdio.h>
   
5. #include <string.h>
   
6. #include <time.h>
   
7. 
   
8. struct item
   
9. {
   
10.         int choosed;
    
11.         int id;
    
12.         int size;
    
13.         int value;
    
14. };
    
15. 
    
16. struct item *create_items(int count)
    
17. {
    
18.         struct item *items;
    
19.         int size;
    
20. 
    
21.         size = count * sizeof(struct item);
    
22.         items = (struct item *)malloc(size);
    
23.         if (items != NULL) {
    
24.                 memset(items, 0, size);
    
25.                 return items;
    
26.         }
    
27.         return NULL;
    
28. }
    
29. 
    
30. int generate_items(struct item *items, int count)
    
31. {
    
32.         int i;
    
33. 
    
34.         memset(items, 0, count * sizeof(struct item));
    
35.         srand(time(NULL));
    
36.         for (i = 0; i < count; ++i) {
    
37.                 items[i].choosed = 0;
    
38.                 items[i].id = i;
    
39.                 items[i].size = rand() % 100 + 1;
    
40.                 items[i].value = rand() % 100;
    
41.         }
    
42.         return 0;
    
43. }
    
44. 
    
45. int release_items(struct item *items)
    
46. {
    
47.         free(items);
    
48.         return 0;
    
49. }
    
50. 
    
51. int compare_item_value(const struct item *item1, const struct item *item2)
    
52. {
    
53.         long data1, data2;
    
54. 
    
55.         data1 = item1->value * item2->size;
    
56.         data2 = item2->value * item1->size;
    
57.         if (data1 < data2) {
    
58.                 return 1;
    
59.         }else if (data1 > data2) {
    
60.                 return -1;
    
61.         }else {
    
62.                 return 0;
    
63.         }
    
64. }
    
65. 
    
66. int compare_item_id(const struct item *item1, const struct item *item2)
    
67. {
    
68.         if (item1->id < item2->id) {
    
69.                 return -1;
    
70.         }else if (item1->id > item2->id) {
    
71.                 return 1;
    
72.         }else {
    
73.                 return 0;
    
74.         }
    
75. }
    
76. 
    
77. int compare_item_c(const struct item *item1, const struct item *item2)
    
78. {
    
79.         if (item1->size < item2->size) {
    
80.                 return -1;
    
81.         }else if (item1->size > item2->size) {
    
82.                 return 1;
    
83.         }else {
    
84.                 return 0;
    
85.         }
    
86. }
    
87. 
    
88. int choose_items(struct item *items, int count, int capability)
    
89. {
    
90.         int i;
    
91. 
    
92.         for (i = 0; i < count; ++i) {
    
93.                 if (items[i].size <= capability) {
    
94.                         items[i].choosed = 1;
    
95.                         capability -= items[i].size;
    
96.                 }
    
97.         }
    
98.         return 0;
    
99. }
    
100. 
     
101. int print_items(struct item *items, int count)
     
102. {
     
103.         int i;
     
104. 
     
105.         for (i = 0; i < count; ++i) {
     
106.                 printf("id=%d, size=%d, value=%d, %d\n", items[i].id, items[i].size, items[i].value, items[i].choosed);
     
107.         }
     
108.         return 0;
     
109. }
     
110. 
     
111. int knapsack_items(struct item *items, int count, int capability)
     
112. {
     
113.         int *f;
     
114.         int *line;
     
115.         int i;
     
116.         int j;
     
117.         int size;
     
118.         int value;
     
119. 
     
120.         size = count * (capability + 1) * sizeof(int);
     
121.         f = (int *)malloc(size);
     
122.         if (f != NULL) {
     
123.                 memset(f, 0, size);
     
124.                 line = f + (count - 1) * (capability + 1);
     
125.                 for (j = 0; j <= capability; j++) {
     
126.                         if(j < items[count - 1].size) {
     
127.                                 line[j] = 0;
     
128.                         }else {
     
129.                                 line[j] = items[count - 1].value;
     
130.                         }
     
131.                 }
     
132.                 for(i = count - 2; i >= 0; i--) {
     
133.                         line -= capability + 1;
     
134.                         for (j = 0; j <= capability; j++) {
     
135.                                 if(j < items[i].size) {
     
136.                                         line[j] = (line + capability + 1)[j];
     
137.                                 }else {
     
138.                                         line[j] = (line + capability + 1)[j] > (line + capability + 1)[j-items[i].size] + items[i].value ? (line + capability + 1)[j] : (line + capability + 1)[j-items[i].size] + items[i].value;
     
139.                                 }
     
140.                         }
     
141.                 }
     
142.                 value = line[capability];
     
143. 
     
144.                 j = capability;
     
145.                 for(i = 0; i <= count - 2; i++) {
     
146.                         if(f[i * (capability + 1) + j] == f[(i + 1) * (capability + 1) + j]) {
     
147.                                 items[i].choosed = 0;
     
148.                         }else {
     
149.                                 items[i].choosed = 1;
     
150.                                 j = j - items[i].size;
     
151.                         }
     
152.                 }
     
153.                 items[count - 1].choosed = f[(count - 1) * (capability + 1) + j] ? 1 : 0;
     
154.                 free(f);
     
155.                 return value;
     
156.         }
     
157.         return -1;
     
158. }
     
159. 
     
160. int clear_items_choose(struct item *items, int count)
     
161. {
     
162.         int i;
     
163. 
     
164.         for (i = 0; i < count; ++i) {
     
165.                 items[i].choosed = 0;
     
166.         }
     
167.         return 0;
     
168. }
     
169. 
     
170. int sum_choosed_item_value(struct item *items, int count)
     
171. {
     
172.         int i;
     
173.         int sum;
     
174. 
     
175.         sum = 0;
     
176.         for (i = 0; i < count; ++i) {
     
177.                 if (items[i].choosed) {
     
178.                         sum += items[i].value;
     
179.                 }
     
180.         }
     
181.         return sum;
     
182. }
     
183. 
     
184. int sum_choosed_item_capability(struct item *items, int count)
     
185. {
     
186.         int i;
     
187.         int sum;
     
188.        
     
189.         sum = 0;
     
190.         for (i = 0; i < count; ++i) {
     
191.                 if (items[i].choosed) {
     
192.                         sum += items[i].size;
     
193.                 }
     
194.         }
     
195.         return sum;
     
196. }
     
197. 
     
198. int main(void)
     
199. {
     
200.         struct item *items;
     
201.         int count;
     
202.         int capability;
     
203.         int value;
     
204.         int a_value;
     
205.         int cnt;
     
206. 
     
207.         count = 10;
     
208.         capability = 100;
     
209.         printf("Please Input (Count, Capability): ");
     
210.         scanf("%d %d", &count, &capability);
     
211.         printf("N=%d, V=%d\n", count, capability);
     
212.         items = create_items(count);
     
213.         if (items != NULL) {
     
214.                 cnt = 1;
     
215.                 do {
     
216.                         generate_items(items, count);
     
217.                         printf("-------------- ITEM %d -------------\n", cnt);
     
218. 
     
219.                         qsort(items, count, sizeof(struct item), (int(*)(const void*,const void*))compare_item_value);
     
220.                         choose_items(items, count, capability);
     
221.                         print_items(items, count);
     
222.                         a_value = sum_choosed_item_value(items, count);
     
223.                         printf("Choosed value: %d\n", a_value);
     
224.                         printf("SUM choosed capability: %d\n", sum_choosed_item_capability(items, count));
     
225. 
     
226.                         clear_items_choose(items, count);
     
227.                         value = knapsack_items(items, count, capability);
     
228.                         print_items(items, count);
     
229.                         printf("KNAPSACK VALUE: %d\n", value);
     
230.                         printf("SUM choosed capability: %d\n", sum_choosed_item_capability(items, count));
     
231.                         ++cnt;
     
232.                 }while (a_value == value);
     
233.                 release_items(items);
     
234.                 return 0;
     
235.         }
     
236.         return -1;
     
237. }
     

复制代码

fender0107401

cobras 发表于 2014-08-30 14:25
发个背包问题贪心算法与动态规划比较。少数情况下贪心算法不能求最佳答案。

哥们，我刚刚也实现了一个贪心算法和动态规划的对比，只要很少的情况下，贪心算法是不能得到最优解的，而且即使得不到最优解，也是相差很小的。

我实现了Matlab和C++两个版本。。。

fender0107401

回复 12# cobras

有空帮我看看，不保证对错，不过咱俩的结论基本一致。

http://bbs.chinaunix.net/thread-4152500-1-1.html

   

patagonia2

哈哈。这个问题，
有意思，我感觉百思不得其解。