动态规划1.2 购物车选物品

问题：

购物车中有n件商品，现有满减条件为满200减50，从购车中选出一些商品，让选出来的商品最大程度的接近满减条件。

分析：

选一些商品，让商品的价格大于200，并且尽量的接近200。

这是一个多阶段决策问题，每个阶段会对应一个状态集合，阶段n的状态可以由阶段 n-1、n-2、...、1 转移而来。

因为所选物品的总价格没有规定一个上限，我们规定为1001，因为物品总价格超过1000，满减的意义就不大了。

这样我们申请的二维状态数组每一列就为1001 + 1。

代码：

 1 #include <iostream>
 2 #include <stack>
 3 
 4 int main()
 5 {
 6     int full = 200;      // 满减条件 
 7     int threshold = 1001;  // 总价超过1001就不考虑了
 8     int items[10] = {22, 33, 44, 23, 25, 90, 80, 2, 43, 16};   //购物车共有10个商品，数组中为每个商品的价值
 9     
10     int states[10][threshold + 1] = {0};
11     
12     if(items[0] < threshold + 1)
13         states[0][items[0]] = 1;
14     
15     for(int i = 1; i < sizeof(items) / sizeof(int); i++)
16     {
17         for(int j = 0; j < threshold + 1; j++)  // 不放入第i个物品
18         {
19             states[i][j] = states[i-1][j];
20         }
21         
22         for(int j = 0; j < threshold + 1; j++)  // 放入第i个物品
23         {
24             if(j + items[i] < threshold + 1)
25             {
26                 if(states[i-1][j] == 1)
27                     states[i][j + items[i]] = 1;
28             }
29         }
30     }
31     
32     int value = 10000;
33     for(int j = 200; j <= threshold; j++)
34     {
35         if(states[9][j] == 1)
36         {
37             value = j;
38             break;
39         }
40     }
41 
42     std::stack<int> s;
43     
44     int right = value;
45     for(int i = 9; i >= 0; i--)
46     {
47         for(int j = right; j >= 0; j--)
48         {
49             if(states[i][j] == 1)
50             {
51                 if(i - 1 >= 0)
52                 {
53                     if(j - items[i] >= 0 && states[i - 1][j-items[i]] == 1)
54                     {
55                         //std::cout << "i:" << i << ", j" << j << "  item :" << items[i] << std::endl;
56                         s.push(items[i]);
57                         right = j - items[i];
58                         break;
59                     }
60                     else
61                         break;
62                 }
63                 else
64                 {
65                     s.push(items[i]);
66                     break;
67                 }
68             }
69         }
70     }
71     
72     std::cout << "value : " << value << std::endl;
73     
74     std::cout << "items : ";
75     while(!s.empty())
76     {
77         std::cout << s.top() << " ";
78         s.pop();
79     }
80     std::cout << std::endl;
81     
82     
83     return 0;
84 }

运行结果：