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

看板C_and_CPP (C/C++)作者deepdish (D 調的華麗)時間18年前 (2006/03/25 12:22)推噓0(0推 0噓 0→)

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

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; } -- 歡迎大家一起加入Intel Philanthropic Peer-to-Peer Program !!! 這項「英特爾慈善『點對點連線』計畫」旨在經由網際網路，把數百萬部個人電腦連結起來，加速研發治療白血球過多症（血癌）的藥物，從而把新藥上市的需要時間縮短約一半。對本計畫有興趣者，可以到http://www.grid.org/download/gold/download.htm 網站，下載該程式。一旦一批資料處理完畢，下次電腦連接上網際網路時，不論經由寬頻或撥接，電腦便會 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.200.77