首先，先来看看我对问题的理解有没有错 以假设有四种包装而言，不一定要四种全部用到， 例如只用两种或三种包装，只要满足最後要的结果(即三种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