动态规划的 01背包问题

佚名 6年前 (2019-04-25) 随笔 1138人围观抢沙发百度已收录

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int w[1000] = { 0 };
 5 int v[1000]    = { 0 };
 6 int h[1000][1000] = { 0 };
 7 int n;
 8 int limit;
 9 int item[1000] = {0};
10 void findmax()
11 {
12     int i,j;
13     for (i = 1; i <= n; ++i)
14     {
15         for (j = 1; j <= limit; ++j)
16         {
17             if (j < w[i])
18                 h[i][j] = h[i - 1][j];
19             else
20                 h[i][j] = max(h[i - 1][j], h[i - 1][j - w[i]] + v[i]);
21         }
22     }
23 }
24 void findwhat(int i, int j)
25 {
26     if (i > 0)
27     {
28         if (h[i][j] == h[i - 1][j])
29         {
30             item[i] = 0;
31             findwhat(i - 1, j);
32         }
33         else if(h[i][j]==h[i-1][j-w[i]]+v[i]&&j-w[i]>=0)
34         {
35             item[i] = 1;
36             findwhat(i-1,j-w[i]);
37         }
38     }
39 }
40 int main(void)
41 {
42     cout << "请输入物品总数n和限制重量limit：";
43     cin >> n >> limit;
44     int i;
45     cout << "请依次输入个物品的重量和价值：" << endl;
46     for (i = 1; i <= n; ++i)
47     {
48         cin >> w[i];
49         cin >> v[i];
50     }
51     findmax();
52     findwhat(n, limit);
53     cout << "价值最多是：" << h[n][limit] << endl;
54     for (i = 1; i <= n; ++i)
55         cout << item[i]<<"  ";
56     return 0;
57 }

。。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int w[1000] = { 0 };
 5 int v[1000]    = { 0 };
 6 int h[1000] = { 0 };
 7 int n;
 8 int limit;
 9 void findmax()
10 {
11     int i,j;
12     for (i = 1; i <= n; ++i)
13     {
14         for (j = limit; j >= 1; --j)
15         {
16             if(j>=w[i])
17                 h[j] = max(h[j], h[j - w[i]] + v[i]);
18         }
19     }
20 }
21 int main(void)
22 {
23     cout << "请输入物品总数n和限制重量limit：";
24     cin >> n >> limit;
25     int i;
26     cout << "请依次输入个物品的重量和价值：" << endl;
27     for (i = 1; i <= n; ++i)
28     {
29         cin >> w[i];
30         cin >> v[i];
31     }
32     findmax();
33     cout << "价值最多是：" << h[limit] << endl;
34     return 0;
35 }