算了算了，我错了，以后不这么玩了。

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 c;
    
13.         int w;
    
14. };
    
15. 
    
16. struct item *create_items(int n)
    
17. {
    
18.         struct item *items;
    
19.         int size;
    
20.         int i;
    
21. 
    
22.         size = n * sizeof(struct item);
    
23.         items = (struct item *)malloc(size);
    
24.         if (items != NULL) {
    
25.                 memset(items, 0, size);
    
26.                 srand(time(NULL));
    
27.                 for (i = 0; i < n; ++i) {
    
28.                         items[i].choosed = 0;
    
29.                         items[i].id = i;
    
30.                         items[i].c = rand() % 100 + 1;
    
31.                         items[i].w = rand() % 100;
    
32.                 }
    
33.                 return items;
    
34.         }
    
35.         return NULL;
    
36. }
    
37. 
    
38. int release_items(struct item *items)
    
39. {
    
40.         free(items);
    
41.         return 0;
    
42. }
    
43. 
    
44. int compare_item_value(const struct item *item1, const struct item *item2)
    
45. {
    
46.         long data1, data2;
    
47. 
    
48.         data1 = item1->w * item2->c;
    
49.         data2 = item2->w * item1->c;
    
50.         if (data1 < data2) {
    
51.                 return 1;
    
52.         }else if (data1 > data2) {
    
53.                 return -1;
    
54.         }else {
    
55.                 return 0;
    
56.         }
    
57. }
    
58. 
    
59. int compare_item_id(const struct item *item1, const struct item *item2)
    
60. {
    
61.         if (item1->id < item2->id) {
    
62.                 return -1;
    
63.         }else if (item1->id > item2->id) {
    
64.                 return 1;
    
65.         }else {
    
66.                 return 0;
    
67.         }
    
68. }
    
69. 
    
70. int choose_items(struct item *items, int n, int v)
    
71. {
    
72.         int i;
    
73. 
    
74.         for (i = 0; i < n; ++i) {
    
75.                 if (items[i].c <= v) {
    
76.                         items[i].choosed = 1;
    
77.                         v -= items[i].c;
    
78.                 }
    
79.         }
    
80.         return 0;
    
81. }
    
82. 
    
83. int print_items(struct item *items, int n)
    
84. {
    
85.         int i;
    
86. 
    
87.         for (i = 0; i < n; ++i) {
    
88.                 printf("id=%d, c=%d, w=%d, %s\n", items[i].id, items[i].c, items[i].w, items[i].choosed ? "CHOOSED" : "");
    
89.         }
    
90.         return 0;
    
91. }
    
92. 
    
93. int main(void)
    
94. {
    
95.         struct item *items;
    
96.         int n;
    
97.         int v;
    
98. 
    
99.         n = 10;
    
100.         v = 100;
     
101.         printf("Please Input (N,V): ");
     
102.         scanf("%d %d", &n, &v);
     
103.         printf("N=%d, V=%d\n", n, v);
     
104.         items = create_items(n);
     
105.         if (items != NULL) {
     
106.                 puts("SOURCE ITEMS:");
     
107.                 print_items(items, n);
     
108.                 qsort(items, n, sizeof(struct item), compare_item_value);
     
109.                 puts("SORTED ITEMS:");
     
110.                 print_items(items, n);
     
111.                 choose_items(items, n, v);
     
112.                 qsort(items, n, sizeof(struct item), compare_item_id);
     
113.                 puts("CHOOSED ITEMS:");
     
114.                 print_items(items, n);
     
115.                 release_items(items);
     
116.                 return 0;
     
117.         }
     
118.         return -1;
     
119. }
     

复制代码

cobras

当然，因为任何一个东西都装不下。

cobras

回复 45# Susake_

c++适用版。{:3_204:}

1. 
   
2. /* knapsack.c */
   
3. 
   
4. #include <stdlib.h>
   
5. #include <stdio.h>
   
6. #include <string.h>
   
7. #include <time.h>
   
8. 
   
9. struct item
   
10. {
    
11.         int choosed;
    
12.         int id;
    
13.         int c;
    
14.         int w;
    
15. };
    
16. 
    
17. struct item *create_items(int n)
    
18. {
    
19.         struct item *items;
    
20.         int size;
    
21.         int i;
    
22. 
    
23.         size = n * sizeof(struct item);
    
24.         items = (struct item *)malloc(size);
    
25.         if (items != NULL) {
    
26.                 memset(items, 0, size);
    
27.                 srand(time(NULL));
    
28.                 for (i = 0; i < n; ++i) {
    
29.                         items[i].choosed = 0;
    
30.                         items[i].id = i;
    
31.                         items[i].c = rand() % 100 + 1;
    
32.                         items[i].w = rand() % 100;
    
33.                 }
    
34.                 return items;
    
35.         }
    
36.         return NULL;
    
37. }
    
38. 
    
39. int release_items(struct item *items)
    
40. {
    
41.         free(items);
    
42.         return 0;
    
43. }
    
44. 
    
45. int compare_item_value(const struct item *item1, const struct item *item2)
    
46. {
    
47.         long data1, data2;
    
48. 
    
49.         data1 = item1->w * item2->c;
    
50.         data2 = item2->w * item1->c;
    
51.         if (data1 < data2) {
    
52.                 return 1;
    
53.         }else if (data1 > data2) {
    
54.                 return -1;
    
55.         }else {
    
56.                 return 0;
    
57.         }
    
58. }
    
59. 
    
60. int compare_item_id(const struct item *item1, const struct item *item2)
    
61. {
    
62.         if (item1->id < item2->id) {
    
63.                 return -1;
    
64.         }else if (item1->id > item2->id) {
    
65.                 return 1;
    
66.         }else {
    
67.                 return 0;
    
68.         }
    
69. }
    
70. 
    
71. int choose_items(struct item *items, int n, int v)
    
72. {
    
73.         int i;
    
74. 
    
75.         for (i = 0; i < n; ++i) {
    
76.                 if (items[i].c <= v) {
    
77.                         items[i].choosed = 1;
    
78.                         v -= items[i].c;
    
79.                 }
    
80.         }
    
81.         return 0;
    
82. }
    
83. 
    
84. int print_items(struct item *items, int n)
    
85. {
    
86.         int i;
    
87. 
    
88.         for (i = 0; i < n; ++i) {
    
89.                 printf("id=%d, c=%d, w=%d, %s\n", items[i].id, items[i].c, items[i].w, items[i].choosed ? "CHOOSED" : "");
    
90.         }
    
91.         return 0;
    
92. }
    
93. 
    
94. int main(void)
    
95. {
    
96.         struct item *items;
    
97.         int n;
    
98.         int v;
    
99. 
    
100.         n = 10;
     
101.         v = 100;
     
102.         printf("Please Input (N,V): ");
     
103.         scanf("%d %d", &n, &v);
     
104.         printf("N=%d, V=%d\n", n, v);
     
105.         items = create_items(n);
     
106.         if (items != NULL) {
     
107.                 puts("SOURCE ITEMS:");
     
108.                 print_items(items, n);
     
109.                 qsort(items, n, sizeof(struct item), (int(*)(const void*,const void*))compare_item_value);
     
110.                 puts("SORTED ITEMS:");
     
111.                 print_items(items, n);
     
112.                 choose_items(items, n, v);
     
113.                 qsort(items, n, sizeof(struct item), (int(*)(const void*,const void*))compare_item_id);
     
114.                 puts("CHOOSED ITEMS:");
     
115.                 print_items(items, n);
     
116.                 release_items(items);
     
117.                 return 0;
     
118.         }
     
119.         return -1;
     
120. }
     

复制代码

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 c;
    
13.         int w;
    
14. };
    
15. 
    
16. struct item *create_items(int n)
    
17. {
    
18.         struct item *items;
    
19.         int size;
    
20.         int i;
    
21. 
    
22.         size = n * sizeof(struct item);
    
23.         items = (struct item *)malloc(size);
    
24.         if (items != NULL) {
    
25.                 memset(items, 0, size);
    
26.                 srand(time(NULL));
    
27.                 for (i = 0; i < n; ++i) {
    
28.                         items[i].choosed = 0;
    
29.                         items[i].id = i;
    
30.                         items[i].c = rand() % 100 + 1;
    
31.                         items[i].w = rand() % 100;
    
32.                 }
    
33.                 return items;
    
34.         }
    
35.         return NULL;
    
36. }
    
37. 
    
38. int release_items(struct item *items)
    
39. {
    
40.         free(items);
    
41.         return 0;
    
42. }
    
43. 
    
44. int compare_item_value(const struct item *item1, const struct item *item2)
    
45. {
    
46.         long data1, data2;
    
47. 
    
48.         data1 = item1->w * item2->c;
    
49.         data2 = item2->w * item1->c;
    
50.         if (data1 < data2) {
    
51.                 return 1;
    
52.         }else if (data1 > data2) {
    
53.                 return -1;
    
54.         }else {
    
55.                 return 0;
    
56.         }
    
57. }
    
58. 
    
59. int compare_item_id(const struct item *item1, const struct item *item2)
    
60. {
    
61.         if (item1->id < item2->id) {
    
62.                 return -1;
    
63.         }else if (item1->id > item2->id) {
    
64.                 return 1;
    
65.         }else {
    
66.                 return 0;
    
67.         }
    
68. }
    
69. 
    
70. int choose_items(struct item *items, int n, int v)
    
71. {
    
72.         int i;
    
73. 
    
74.         for (i = 0; i < n; ++i) {
    
75.                 if (items[i].c <= v) {
    
76.                         items[i].choosed = 1;
    
77.                         v -= items[i].c;
    
78.                 }
    
79.         }
    
80.         return 0;
    
81. }
    
82. 
    
83. int print_items(struct item *items, int n)
    
84. {
    
85.         int i;
    
86. 
    
87.         for (i = 0; i < n; ++i) {
    
88.                 printf("id=%d, c=%d, w=%d, %s\n", items[i].id, items[i].c, items[i].w, items[i].choosed ? "CHOOSED" : "");
    
89.         }
    
90.         return 0;
    
91. }
    
92. 
    
93. int knapsack_items(struct item *items, int N, int V)
    
94. {
    
95.         int *f;
    
96.         int i;
    
97.         int v;
    
98.         int size;
    
99.         int value;
    
100. 
     
101.         size = (V + 1) * sizeof(int);
     
102.         f = (int *)malloc(size);
     
103.         if (f != NULL) {
     
104.                 memset(f, 0, size);
     
105.                 for(i = 0; i < N; ++i) {
     
106.                         for(v = V; v >= items[i].c; --v) {
     
107.                                 value = f[v - items[i].c] + items[i].w;
     
108.                                 if (value > f[v]) {
     
109.                                         f[v] = value;
     
110.                                 }
     
111.                         }
     
112.                 }
     
113.                 value = f[V];
     
114.                 free(f);
     
115.                 return value;
     
116.         }
     
117.         return -1;
     
118. }
     
119. 
     
120. int clear_items_choose(struct item *items, int n)
     
121. {
     
122.         int i;
     
123. 
     
124.         for (i = 0; i < n; ++i) {
     
125.                 items[i].choosed = 0;
     
126.         }
     
127.         return 0;
     
128. }
     
129. 
     
130. int sum_choosed_item(struct item *items, int n)
     
131. {
     
132.         int i;
     
133.         int sum;
     
134. 
     
135.         sum = 0;
     
136.         for (i = 0; i < n; ++i) {
     
137.                 if (items[i].choosed) {
     
138.                         sum += items[i].w;
     
139.                 }
     
140.         }
     
141.         return sum;
     
142. }
     
143. 
     
144. int main(void)
     
145. {
     
146.         struct item *items;
     
147.         int n;
     
148.         int v;
     
149.         int value;
     
150. 
     
151.         n = 10;
     
152.         v = 100;
     
153.         printf("Please Input (N,V): ");
     
154.         scanf("%d %d", &n, &v);
     
155.         printf("N=%d, V=%d\n", n, v);
     
156.         items = create_items(n);
     
157.         if (items != NULL) {
     
158.                 puts("SOURCE ITEMS:");
     
159.                 print_items(items, n);
     
160.                 qsort(items, n, sizeof(struct item), (int(*)(const void*,const void*))compare_item_value);
     
161.                 puts("SORTED ITEMS:");
     
162.                 print_items(items, n);
     
163.                 choose_items(items, n, v);
     
164.                 qsort(items, n, sizeof(struct item), (int(*)(const void*,const void*))compare_item_id);
     
165.                 puts("CHOOSED ITEMS:");
     
166.                 print_items(items, n);
     
167.                 printf("SUM choosed value: %d\n", sum_choosed_item(items, n));
     
168. 
     
169.                 clear_items_choose(items, n);
     
170.                 value = knapsack_items(items, n, v);
     
171.                 puts("KNAPSACK CHOOSED ITEMS:");
     
172.                 print_items(items, n);
     
173.                 printf("KNAPSACK VALUE: %d\n", value);
     
174.                 release_items(items);
     
175.                 return 0;
     
176.         }
     
177.         return -1;
     
178. }
     

复制代码