Re: [問題] 好像是整數線性規劃的問題 10089 level 2

看板C_and_CPP (C/C++)作者gavintsou (打網球囉)時間18年前 (2006/03/25 22:27)推噓4(4推 0噓 4→)

留言8則, 3人參與討論串2/2 (看更多)

首先，先來看看我對問題的理解有沒有錯以假設有四種包裝而言，不一定要四種全部用到，例如只用兩種或三種包裝，只要滿足最後要的結果(即三種size數量一樣) 如果問題不是這樣，那不用往下看了 @@ -------------------------------------------- 假設有n種包裝，用y[n]來存放 0~3，0即未使用此包裝，依此類推 (不確定題目有無係數規定，因為看到最高係數為3) x1[n]、x2[n]、x3[n]來存放每一個包裝的數量所以就.....寫個迴圈 ex: n=4 ( y[1], y[2], y[3], y[4] ) = (1, 0, 0, 0) = (0, 1, 0, 0) = (0, 0, 1, 0) ...... ...... ...... = (3, 3, 3, 3) 在每一次回合中，判斷三種數量是否相同例如可以直接先算出一個值 Cup_Num = x1[i]*y[1]; i=0~3 (因為目前有四種包裝) 再去比較與x2[i]*y[1]及x3[i]*y[1]是否相同 (即三種數量是否相同) 否：next iteration 是：恭喜，至少存在一解不知道這樣的想法有沒有錯，本來是要直接寫程式，但是太懶了 = = PS.一開始看到整數規劃，以為在討論branch and bound......@@ ※ 引述《deepdish (D 調的華麗)》之銘言： : http://online-judge.uva.es/p/v100/10089.html : 稍微翻譯一下題目 : -------------------------------------------------------------------------- : 咖啡杯有三種大小 : 但最近發現有很大需求包裝相同數量的三種杯子 : 所以為了趕緊符合要求 ACM 決定要將一些未銷售產品包裝拆開 : 重新包裝為相同數量的三種杯子， : 而且不能有未包裝杯子剩下 : 找出這種組合是否存在 : --------------------------------------------------------------------------- : 假設有四種包裝 (1, 2, 3), (1, 11, 5), (9, 4, 3), (2, 3, 2). : (1,11,5) 代表這個包裝中第一種咖啡杯 1 個，第二種咖啡杯 11 個，第三種咖啡杯 5 個 : 剛好找到一解，第一種包裝三包 + 第三種包裝一包 + 第四種包裝兩包，如下： : 3 * (1,2,3) + (9,4,3) + 2 * (2,3,2) == 16 * (1,1,1) : 另外一個範例：假設有四種包裝 (1, 3, 3), (1, 11, 5), (9, 4, 3), (2, 3, 2) : 但是沒有解 : 請問高手要怎麼解這一題︿︿？ : 用了高中數學的克拉馬法則每次挑三個不同包裝去解 : 答案和範例輸入輸出一樣 : 可是答案上傳到線上判斷是錯誤的 >.<~ : 問了好多人，想了很多天還是解不出來...... : 錯誤的程式碼如下： : #ifndef ONLINE_JUDGE : #include <fstream> : #endif : #include <iostream> : using namespace std; : bool check(int p, int q) : { // 檢查分數是否為正數 : if(p > 0 && q >= 0) : return true; : else if(p < 0 && q <= 0) : return true; : else : return false; : } : int main() : { : #ifndef ONLINE_JUDGE : ifstream cin("ACM10089.txt"); : #endif : int c, d, d1, d2, d3, i, j, k, n, x, y, z; : bool ans; : while( cin >> n ) : { : if(n == 0) : break; : ans = false; : int a[n][3]; : //c = n * (n - 1) * (n - 2) / 6; : //cout << "c = " << c << endl; : for(i = 0; i < n; i++) : for(j = 0; j < 3; j++) : cin >> a[i][j]; : //for(i = 0; i < n; i++, cout << endl) : //for(j = 0; j < 3; j++) : //cout << a[i][j] << " "; : for(i = 0; i < n - 2; i++) // 0-1 : { : for(j = i + 1; j < n - 1; j++) // 1-2 : { : for(k = j + 1; k < n; k++) // 2-3 : { : for(x = 0, d = 0; x < 3; x++) : { : y = (x + 1 == 3) ? 0 : x + 1; : z = (x + 2 > 2) ? x - 1 : x + 2; : d += a[i][x] * a[j][y] * a[k][z]; : d -= a[k][x] * a[j][y] * a[i][z]; : } : //cout << "d = " << d << endl; : if(d == 0) // 分母不得為零 : break; : for(x = 0, d1 = 0; x < 3; x++) : { : y = (x + 1 == 3) ? 0 : x + 1; : z = (x + 2 > 2) ? x - 1 : x + 2; : d1 += 1 * a[j][y] * a[k][z]; : d1 -= a[k][x] * a[j][y] * 1; : } : //cout << "d1 = " << d1 << endl; : if(check(d, d1)== false) : break; : for(x = 0, d2 = 0; x < 3; x++) : { : y = (x + 1 == 3) ? 0 : x + 1; : z = (x + 2 > 2) ? x - 1 : x + 2; : d2 += a[i][x] * 1 * a[k][z]; : d2 -= a[k][x] * 1 * a[i][z]; : } : //cout << "d2 = " << d2 << endl; : if(check(d, d2)== false) : break; : for(x = 0, d3 = 0; x < 3; x++) : { : y = (x + 1 == 3) ? 0 : x + 1; : z = (x + 2 > 2) ? x - 1 : x + 2; : d3 += a[i][x] * a[j][y] * 1; : d3 -= 1 * a[j][y] * a[i][z]; : } : //cout << "d3 = " << d3 << endl; : if(check(d, d3)== false) : break; : ans = true; : } : if(ans) : break; : } : if(ans) : break; : } : if(ans) : cout << "Yes" << endl; : else : cout << "No" << endl; : } : #ifndef ONLINE_JUDGE : system("pause"); : #endif : return 0; : } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.111.146