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

Susake_

这个是??3个物品,容量为2...

cobras

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

Susake_

我也来一个贪心的(是Codeforces上的一个题目,不过是每个物品只有容量1和2两个值)

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct Node
   
5. {
   
6.     int w;
   
7.     int num;
   
8. };
   
9. 
   
10. Node Susake[100006];
    
11. Node dp[100006];
    
12. int a[100006];
    
13. 
    
14. int comp(Node a, Node b)
    
15. {
    
16.     return a.w > b.w ? 1 : 0;
    
17. }
    
18. 
    
19. int main(int argc, char *argv[])
    
20. {
    
21.     int n, v, v1, v2, t1, t2;
    
22.     memset(Susake, 0, sizeof(Susake));
    
23.     memset(dp, 0, sizeof(dp));
    
24.     scanf("%d%d", &n, &v);
    
25.     t1 = t2 = 0;
    
26.     for(int i = 1; i <= n; i++)
    
27.     {
    
28.         scanf("%d%d", &v1, &v2);
    
29.         if(v1 == 1)
    
30.         {
    
31.             t1++;
    
32.             Susake[t1].w = v2;
    
33.             Susake[t1].num = i;
    
34.         }
    
35.         else
    
36.         {
    
37.             t2++;
    
38.             dp[t2].w = v2;
    
39.             dp[t2].num = i;
    
40.         }
    
41.     }
    
42.     sort(Susake + 1, Susake + t1 + 1, comp);
    
43.     sort(dp + 1, dp + t2 + 1, comp);
    
44.     int k1 = 1, k2 = 1, j = 0, weight = 0;
    
45.     memset(a, 0, sizeof(a));
    
46.     if(v % 2 == 1 && Susake[k1].w * 2> dp[k2].w && v >= 1 && k1 <= t1)
    
47.     {
    
48.         weight += Susake[k1].w;
    
49.         j++;
    
50.         a[j] = Susake[k1].num;
    
51.         k1++;
    
52.         v--;
    
53.     }
    
54.     while(v)
    
55.     {
    
56.         if(k1 > t1 && k2 > t2) break;
    
57.         if(k1 + 1 <= t1 && k2 <= t2 && v >= 2)
    
58.         {
    
59.             if(Susake[k1].w + Susake[k1 + 1].w > dp[k2].w)
    
60.             {
    
61.                 weight += Susake[k1].w + Susake[k1 + 1].w;
    
62.                 j++;
    
63.                 a[j] = Susake[k1].num;
    
64.                 j++;
    
65.                 a[j] = Susake[k1 + 1].num;
    
66.                 k1 += 2;
    
67.                 v -= 2;
    
68.             }
    
69.             else
    
70.             {
    
71.                 weight += dp[k2].w;
    
72.                 j++;
    
73.                 a[j] = dp[k2].num;
    
74.                 k2++;
    
75.                 v -= 2;
    
76.             }
    
77.         }
    
78.         else if(k2 <= t2 && v >= 2 && k1 + 1 > t1)
    
79.         {
    
80.             weight += dp[k2].w;
    
81.             j++;
    
82.             a[j] = dp[k2].num;
    
83.             k2++;
    
84.             v -= 2;
    
85.         }
    
86.         else if(k2 > t2 && v >= 1 && k1 <= t1)
    
87.         {
    
88.             weight += Susake[k1].w;
    
89.             j++;
    
90.             a[j] = Susake[k1].num;
    
91.             k1++;
    
92.             v--;
    
93.         }
    
94.         else
    
95.         {
    
96.             if(k1 <= t1 && v >= 1)
    
97.             {
    
98.                 weight += Susake[k1].w;
    
99.                 j++;
    
100.                 a[j] = Susake[k1].num;
     
101.                 k1++;
     
102.                 v--;
     
103.             }
     
104.             else if(k2 <= t2 && v >= 2)
     
105.             {
     
106.                 weight += dp[k2].w;
     
107.                 j++;
     
108.                 a[j] = dp[k2].num;
     
109.                 k2++;
     
110.                 v -= 2;
     
111.             }
     
112.             else break;
     
113.         }
     
114.     }
     
115.     printf("%d\n", weight);
     
116.     if(j > 0)
     
117.     {
     
118.         if(j == 1)
     
119.             printf("%d\n", a[1]);
     
120.         else
     
121.         {
     
122.             for(int i = 1; i <= j - 1; i++)
     
123.                 printf("%d ", a[i]);
     
124.             printf("%d\n", a[j]);
     
125.         }
     
126.     }
     
127.     return 0;
     
128. }
     

复制代码

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

复制代码

fender0107401

算了，还是编辑掉吧。

Susake_

回复 55# fender0107401

学生,平时闲的时候弄弄~
   

Kurosaki_Ichigo

上面的C代码同之前的m代码用的是同样的算法，优先选取价值与质量比最高的放入背包。这种贪心算法效率很高，进行一次排序和一次扫描就能完成，但很多时候只能得到近似解，并不能得到最优解，所以也是错的

fender0107401

__BlueGuy_ 发表于 2014-08-28 10:56
真有意思！我用的着去裸奔么？你以为你有水平可以让我裸奔么？
这么一个简单的基础题，walleeee、star ...

hi，3，早上吃了吗？

cjaizss

__BlueGuy_ 发表于 2014-08-28 10:56
真有意思！我用的着去裸奔么？你以为你有水平可以让我裸奔么？
这么一个简单的基础题，walleeee、star ...

三爷,悄悄的说一句,那个东西叫matlab