今天北京电子科技学院的一网友问我一题，我面熟，说用dp，可发现自己对dp理解不是很好，现在拿出买的《ACM程序设计培训教程》看到背包问题有那么多解法，现在学习中……
小明假期同爸爸一起去书店，他选中了n本书，每本书的单价分别为：P1、P2、P3……Pn。不巧的是，小明的爸爸只带了M元钱，为了让小明渡过一个愉快的假期，爸爸仍然同意买书，但有一个要求，要小明从n本书中选出若干本，使得单价相加所得的和同M元最接近。你能够帮助小明解决这个问题吗？
要求：总钱数M、书本数n以及各本书的价格从键盘或文件输入；如果有多种组合，应全部列出。 现在还有一个要求：就是小明对每一种书都有一个兴趣度，从键盘输入，如果有相同的总价格，则考虑他们的总兴趣度，选择兴趣度大的输出。
Code
1
#include <stdio.h>
2
3#define MAX 51
4struct booksinfo
5
{
6
float price;
7 float v;
8 int flag;
9
}books[MAX];
10
11int main(void)
12{
13 int i, j, k, m, n;
14 int a[MAX];//标志要哪几本
15 float total;
16 int count = 0, pn;
17 float max = -1, sum;
18
19 printf("input number of money: ");
20 scanf("%f", &total);
21 printf("input number of books: ");
22 scanf("%d", &n);
23 printf("input price and value: ");
24 for (i = 0; i < n; i++)
25
{
26 scanf("%f%f", &books[i].price,&books[i].v);
27 books[i].flag = i+1;
28
}
29
30 m = 1;
31 k = 1;
32 for (i = 1; i < n; i++)//枚举
33 {
34 m = m * 2 + 1;
35 k <<= 1;
36 }
37
38 for (i = 1; i <= m; i++)//符合i的取书情况的就统计
39 {
40 pn = 0;
41 sum = 0;
42 for (j = 1; j <= k; j <<= 1)
43 {
44 if ((i & j) == j)
45 {
46 sum += books[pn].price;
47 if (sum > total)
48 break;
49 }
50 pn++;
51 }
52
53 if (sum <= total)
54 {
55 if (sum > max)
56 {
57 count = 1;
58 a[count - 1] = i;
59 max = sum;
60 }
61 else if (sum == max)//增加一种
62 {
63 count++;
64 a[count - 1] = i;
65 }
66 }
67 }
68
69 printf("%d groups\n", count);
70max = 0;
71for (i = 0; i < count; i++)
72 {
73 sum = 0;
74 pn = 0;
75 for (j = 1; j <= k; j <<= 1)
76 {
77 if ((a[i] & j) == j)//与a[i]取书相同的情况就输出
78 {
79 printf("%f ", books[pn].price);
80 sum += books[pn].v;
81 }
82 pn++;
83 }
84 if (sum > max)
85 {
86 m = a[i];
87 max = sum;
88 }
89 printf("\n");
90 }
91 printf("the max interesting:\n");
92 for (j = 1; j <= k; j <<= 1)
93 {
94 pn = 0;
95 if ((m & j) == j)
96 printf("%f ", books[pn].price);
97 pn++;
98 }
99 printf("\n");
100// system("pause");
101}
102