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

fender0107401

话说，我从来就没打算真让3出去裸奔。

blue_guy

恶心！


技术论坛混讲究的是艺压当行人，

你要写出来一份让大家都认可的代码以后，不让BlueGuy去裸奔，那是你高风亮节。

现在这种和稀泥的手段，只能让人觉得你恶心。

要么，你认真的写份代码，要么，你诚恳的承认不行，都算你为人光棍，

唱这么一出，真叫人恶心。

fender0107401

blue_guy 发表于 2014-08-28 09:02
恶心！

好，我技术差，人品差，没能力。

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

复制代码

Susake_

试了VS2013和Codeblocks都无法正常编译的?~

1. 1>c:\users\susake\desktop\win32project1\win32project1\源.cpp(118): error C2664: “void qsort(void *,size_t,size_t,int (__cdecl *)(const void *,const void *))”: 无法将参数 4 从“int (__cdecl *)(const item *,const item *)”转换为“int (__cdecl *)(const void *,const void *)”
   
2. 1>          在匹配目标类型的范围内没有具有该名称的函数
   
3. 1>c:\users\susake\desktop\win32project1\win32project1\源.cpp(122): error C2664: “void qsort(void *,size_t,size_t,int (__cdecl *)(const void *,const void *))”: 无法将参数 4 从“int (__cdecl *)(const item *,const item *)”转换为“int (__cdecl *)(const void *,const void *)”
   
4. 1>          在匹配目标类型的范围内没有具有该名称的函数

复制代码

hellioncu

Susake_ 发表于 2014-08-28 10:30
试了VS2013和Codeblocks都无法正常编译的?~

用   .c，别用.cpp

Susake_

回复 46# hellioncu
嗯,thx

   

cokeboL

楼主给力，坐等视频

fender0107401

都散了吧，上面那个C代码不是我贴的，3不用去裸奔。

fender0107401