整數規劃 (2) @ Edison.X. Blog

第二個問題

假設 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;
}