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

考慮一個簡單的問題
x+Y <= 3，其中 x, y 為大於等於 0 之整數，要把所有符合條件的 x, y 都列出來。
這問題只是簡單的 trackback ，用 recursive 很快可得到解答，說明有空再寫。
原始碼如下