0-1背包问题的动态规划解法之二位数组

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int num[4] = { 2, 2, 4, 6 };
 5 int f()
 6 {
 7     bool state[5][6];  //在linux中注意用memset(state,false,sizeof(state))初始化；这里可以不用，因为自动被初始化为false
 8     state[0][0] = true;
 9 
10     for (int i = 1; i < 5; i++)   
11     {
12         for (int j = 0; j <=5; j++)    //物品不装入背包
13         {
14             if (state[i - 1][j] == true)
15                 state[i][j] = true;
16         }
17 
18         if (num[i] > 5)  //如果本物品重量超过可容纳重量，则继续下一个循环
19             continue;
20 
21         for (int j = 0; j <= 5 - num[i]; j++) //把物品装入背包
22         {
23 
24             if (state[i - 1][j] == true)
25                 state[i][j + num[i]] = true;
26         }
27     }
28 
29     for (int j = 5; j >= 0; j--)  //输出
30     {
31         if (state[4][j] == true)
32             return j;
33     }    
34     return 0;
35  }
36 
37  int main()
38  {
39      int i = f();
40      cout << i << endl;     
41      system("pause");
42      return i;
43  }