第二個問題

假設 1a+2b+3c+4d+5e+6f >=10 且 2a+3b+4c+5d+6e+7f <= 21,其中 a,b,c,d,e,f 都是大於等於 0 的整數,要求符合條件的 abcdef,這裡主要的問題是第一個限制式,因為它是愈加愈大,所以如果用它拿來當主判斷的話會遺失很多可用資訊。這裡用第二式為主判斷,判斷成功後再去判斷第一式合不合條件,原始碼如下

#include <stdio.h>
#include <stdlib.h>

#define N 6
const int coef1[N] = {1,2,3,4,5,6};
const int coef2[N] = {2,3,4,5,6,7};

const int lim1 = 10, lim2 = 21;
int sol[N] = {0};
int sol_cnt=0;


inline void print_sol()
{
    int i;
    printf("Cnt%4d:(", sol_cnt+1);
    for(i=0; i!=N; ++i) printf("%c=%d,", 'a'+i, sol[i]);
    printf(")\n");
    ++sol_cnt;
}
void dfs(int index, int sum1, int sum2)
{
    sum1 += coef1[index]*sol[index];
    sum2 += coef2[index]*sol[index];
    if(index==N-1 && sum2 <= lim2) {// 合條件2
           if(sum1>=lim1) print_sol(); // 合條件1
           // 再試下個數字
           sum1 -= coef1[index]*sol[index];
           sum2 -= coef2[index]*sol[index];
           ++sol[index];
           dfs(index, sum1, sum2);
    }
    else if(sum2<=lim2) {// 暫時合條件2
           dfs(++index, sum1, sum2);
    }
    else{ // 不合條件2
           // 回到上一個狀態, sol[index] 設成0
           sum1-= coef1[index]*sol[index];
           sum2-= coef2[index]*sol[index];
           sol[index]=0;
           --index;
           if(index<0) return; // 結束
           sum1-= coef1[index]*sol[index];
           sum2-= coef2[index]*sol[index];
           ++sol[index];
           dfs(index, sum1, sum2);
    }
}
int main()
{
    dfs(0, 0, 0);
    return 0;
}

最後聲明,所有的線性規劃問題事實上不該用 recursive 這種窮舉法來解 (只是我舉的例子比較特別),大多都會有一個目標式,應要使用單形法或大M 法等求線性規劃之現有方法。

[Lemma]

感謝 Jacob Lee  指出化簡此問題之方法

1a+2b+3c+4d+5e+6f >=10  (1) 
2a+3b+4c+5d+6e+7f <= 21 (2)

(1) * -1 ---> -1a-2b-3c-4d-5e-6f <= -10  (3)
(2) + (3) --> a + b + c + d + e + f <= 11  (4)

直接解 (4) 便可

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()