分类导航

HTML5 发布时间：2022-04-27 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了线性规划算法实现二-----多状态线形规划，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

 1 小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合。

 2 #include "pch.h"
 3 #include <iostream>
 4 using namespace std;
 5 
 6 unsigned long long  test(int K,int N,int M)
 7 {
 8     if (K <= 0 || N <= 0 || M <= 0)return 0;
 9     //一样可计算出结果，但没必要算
10     if (K > N * M)return 0;
11     if (K == N * M)return 1;
12     int L = K < M ? K : M;
13     unsigned int ***p = new  unsigned int**[n];
14     
15     for (int i = 0; i < N; i++)
16     {
17         p[i] = new unsigned int *[L + 1];
18         for (int j = 0; j <= L; j++)
19         {
20             //全初始化为0
21             p[i][j] = new unsigned int[K + 1]();
22         }
23     }
        //此处从0开始是因为列数0用于累计所有的未选择项，简单来说，就是统计跨层迭代，从而可以只观察上一层就可以计算出跨层的累计迭代数          
24     for (int i = 0; i <= L; i++)
25     {
26         p[0][i][i] = 1;
27     }
28     for (int i = 1; i < N; i++)
29     {
30         //吃j串状态
31         for (int j = 0; j <= L; j++)
32         {
33             //吃完总计串数为k
34             for (int k = 0; k <= K; k++)
35             {
36 
37                 for (int l = 0; l <= L; L++)
38                 {
39                     //此轮吃完j串总计k串的方法共有上一轮所有选择剩下k-j的方法数
40                     if (k - j >= 0)
41                         p[i][j][k] += p[i - 1][l][k - j];
42                 }
43             }
44         }
45     }
46     unsigned long long sum = 0;
47     for (unsigned int i = 0; i <= L; i++)
48     {
49         sum += p[N - 1][i][K];
50     }
51     //防止内存泄漏
52     for (int i = 0; i < N; i++)
53     {
54 
55         for (int j = 0; j <= L; j++)
56         {
57             //全初始化为0
58             delete[]p[i][j];
59         }
60         delete[]p[i];
61     }
62     delete[]p;
63     return sum;
64 }
65 
66 int main()
67 {
68 
69     int N,M,K;
70     cout << "请输入要吃的窜数" << endl;
71     cin >> K;
72     cout << "请输入种类数" << endl;
73     cin >> N;
74     cout << "请输入每种的数量" << endl;
75     cin >> M;
76     cout << "一共可以有 " << test(K,N,M) << " 种吃法" << endl;;
77 }

若此题使用函数调用遍历，非常简单，但即使是使用优化剪枝一样可能导致栈溢出

直接遍历法，每次决策吃第i种j串，都得继续遍历余下所有的可能，直至到决策n为止（做了算法剪枝也差不多）

下面即为直接函数调用方法进行遍历

 1 //待优化，数值过大时，栈过深
 2 #include "pch.h"
 3 #include <iostream>
 4 #include<String>
 5 
 6 using namespace std;
 7 /*
 8 
 9 四、小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合
10 //设相同种类同数量为1个点餐组合，即 A1 B19 无论A出现在哪均为一种,那么为了模拟不重复，选择了一种的数量后，后面就不能选择选择过的
11 */
12 unsigned long long f( int n,int left,int M)
13 {
14     
15     //吃完
16     if (left == 0)return 1;
17     //没有下一种了
18     if (n > N)return 0;
19     unsigned long long sum = 0;
20 
21     for (int i = 0; i <=left&&i<=M; i++)
22     {
23         sum =sum+ f(n + 1,left - i,M);
24     }
25     
26     return sum;
27 }
28 unsigned long long test(int K,int M)
29 {
30     unsigned long long result = 0;
31     //非法数据
32     if (K == 0||N==0||M==0)return 0;
33     //没有吃够的吃法
34     if (K > N*M)return 0;
35     //选择第N种烧烤
36     for (int i = 0; i <=M&&i <=K; i++)
37     {
38         result = result + f(2,K-i,M);
39     }
40     return result;
41 }
42 
43 int main()
44 {
45 
46     int N,K;
47     cout << "请输入要吃的窜数" << endl;
48     cin >> K;
49     cout << "请输入种类数" << endl;
50     cin >> N;
51     cout << "请输入每种的数量" << endl;
52     cin >> M;
53     cout << "一共可以有 " << test(K,M) << " 种吃法" << endl;;
54 }