0-1 背包问题有这几个元素：个数、重量、价值。
n 个东西，有各自的重量和价值。一个背包，其最大的可行装载量为 m。
要求，在不超过 m 的情况下，装得最大的价值，并求出具体装了哪些东西。
实现：
1 #include <iostream>
2 using namespace std;
3
4 void solve(int n_weights_values[6][11], int weights[5], int values[5], int n, int m)
5 {
6 int i, j;
7 for (i = 1; i <= n; ++i)
8 {
9
10 for (j = 1; j <= m; ++j)
11 {
12 n_weights_values[i][j] = n_weights_values[i - 1][j];
13 if (weights[i - 1] <= j)
14 {
15 int temp = n_weights_values[i - 1][j - weights[i - 1]] + values[i - 1];
16 if (temp > n_weights_values[i][j])
17 {
18 n_weights_values[i][j] = temp;
19 }
20 }
21 }
22 }
23 }
24
25 void getPaths(int paths[5], int n_weights_values[6][11], int weights[5], int n, int m)
26 {
27 int i, j = m;
28 for (i = n; i > 0; --i)
29 {
30 if (n_weights_values[i][j] > n_weights_values[i - 1][j])
31 {
32 paths[i - 1] = 1;
33 j -= weights[i - 1];
34 }
35 }
36 }
37
38 int main()
39 {
40 int n = 5;
41 int m = 10;
42 int weights[5] = {1, 3, 8, 2, 7};
43 int values[5] = {2, 5, 3, 9, 4};
44 int n_weights_values[6][11];
45 int paths[5];
46 memset(n_weights_values, 0, sizeof (n_weights_values));
47 memset(paths, 0, sizeof (paths));
48
49 solve(n_weights_values, weights, values, n, m);
50 getPaths(paths, n_weights_values, weights, n, m);
51
52 cout << n_weights_values[n][m] << endl;
53 for (int i = 0; i < n; ++i)
54 {
55 if (paths[i] == 1)
56 {
57 cout << i + 1 << ' ' << weights[i] << ' ' << values[i] << endl;
58 }
59 }
60
61 return 0;
62 }
参考：
http://blog.csdn.net/livelylittlefish/archive/2008/03/16/2186206.aspxhttp://www.cnblogs.com/zyobi/archive/2009/06/22/1508730.htmlhttp://hi.bccn.net/space-339919-do-blog-id-14722.htmlhttp://dev.firnow.com/course/3_program/c++/cppsl/2008316/104782.htmlhttp://www.cppblog.com/dawnbreak/archive/2009/08/11/92854.html
posted on 2011-05-15 23:19
unixfy 阅读(253)
评论(0) 编辑 收藏 引用