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

Kurosaki_Ichigo

唉，平板敲字还是慢啊，前贴中说的上一段指的是前一页里第一段c代码。总之01背包就不能用贪心发法

Susake_

回复 61# Kurosaki_Ichigo

是啊，背包用贪心是无法解得最优解的~我那题之所以用贪心，也是题目设计的,数据量是10^6,2重for必超,而特殊的是这题的每个物品容量只有1和2
   

Kurosaki_Ichigo

这贴这么火？在我敲字的时候就多了N贴

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. }
     

复制代码

棉布袋

约瑟夫·维萨里奥诺维奇·斯大林同志说的对。

有理想的人，生活总是火热的。

fender0107401

__BlueGuy_ 发表于 2014-08-28 16:37
大家现在对你的 "专长" 都了解了

hi，3，今天心情怎么样？

fender0107401

__BlueGuy_ 发表于 2014-08-28 16:55
你的技术水平我早就一清二楚了
permofc说的那段话，很明显说的就是你啊
三爷开源的代码都有20000行，难不 ...

行，你不出去裸奔就行，别的都好说。

你牛逼，我们都知道。