Related: LeetCode 473 - Matchsticks to Square
https://uva.onlinejudge.org/external/103/10364.pdf
http://luckycat.kshs.kh.edu.tw/homework/q10364.htm
給你一些棍子的長度，請你算出這些棍子是否可以連成一個正方形（端點對端點，且棍子不可折斷）
每組測試資料一列，第一個整數為M（4 <= M <= 20），代表棍子的數目。接下來的M個整數分別代表這M根棍子的長度，每支棍子的長度介於1到10000之間。
// I solve this problem by DP with bitmask. Each bitmask denotes a set of
// "used" sticks (1 is used, 0 is not). Bitmask 10011 maps to a subset of
// sticks like {31, 24, 17}. (sticks[0] = 31, sticks[1] = 24, sticks[4] = 17).
//
// For each bitmask B, dp[B] stores the max number of groups the
// bitmask can be divided, where each group has sum equals to square's side
// lenght. Side length is calculated by sitcks_sum / 4. In the essence, dp[B]
// stores the max number of sides that B can formed for square.
//
// For example. sticks_sum = 20, side_length = 5 (20 / 4).
// For a bitmask maps to sticks {2, 3, 4, 5, 6}, we can optimally group sticks into
// 2 groups with sum == 5 ({2,3} and {5}), with 4 and 6 not grouped . We name
// the sum of ungrouped sticks "residue". In this case, the residue is 10 (4 +
// 6). It can be observed that if residue > side_length, then it is impossible
// to form square for B.
//
// Lets define sub-bitmask. For bitmask B, sub-bitmask B' is a bitmask deduced
// by flipping any bit in B which is 1 to 0. The number of B' sub-bitmasks
// equals to the number of "1"s in B.
//
// Finally, the dp induction:
// dp[B] = max(dp[B'] + 1 : if residue of B = edge /
// dp[B'] : if residue of B still < edge,
// 0 : if residue of B > edga,
// for all B's sub-bitmask B')
//
// natural ordering to scan B is good for us, since we will meet every B' before B.
//
// Most important, we need some optimizations:
// 1. only need to try half of mask -- we can assume stick[m - 1] is always not used.
// 2. dont precompute anything for all bitmask -- no in dp[], no in value[].
// But vector initalization is fine.
http://wilson100hong.blogspot.com/2015/05/uva-10364-square-dp-solution.html
First of all, let a[i] be the length of i-th stick, and let's define as a bit mask containing N bits which indicates that i-th stick is included in b if b[i] equals to 1, and 0 otherwise. We can first precompute val[b], the sum of all a[i] for which b[i] is set to 1. Furthermore, let's define X be the sum of all a[i] divided by 4. As you can guess, X is the length of each sides of the resulting square in the end. Let D[b] be the number of times we passed a multiple of X. D[b] = k will mean that we can divide N sticks into k groups of total length X each, and possibly one more group with total length less than X. Therefore we have the following relationship:
let K = max { D[b with j-th bit set to 0] }, then
D[b] = K + { 1 if val[b] equals to (K+1)X, and 0 otherwise }
In the end, we will have D[-1] = 4 if and only if there exists a possible partitioning of the sticks into 4 groups of total length X.
To pass the UVa time limit, you need to make use of a symmetry: since every stick must belong to a group, we can without loss of generality set the first stick to be in the first group and proceed as per usual. This optimisation alone will reduce the search time by half.
https://blog.csdn.net/mobius_strip/article/details/51834170
剪枝：1.排序，預處理；
2.如果相同長度前面的沒選，後面的不會選；
3.如果發現構造一根長棍子失敗，則不會成功；
4.在構造一根長棍子時，按照順序取小棍子；
int dfs(int max, int n, int s, int d, int sum)
{
if (d == 3) {
return 1;
}
for (int i = s; i < n; ++ i) {
if (visit[i] || i && !visit[i-1] && stick[i] == stick[i-1]) {
continue;
}
visit[i] = 1;
if (sum + stick[i] == max) {
if (dfs(max, n, 0, d+1, 0)) {
return 1;
}
}else if (sum + stick[i] < max) {
if (dfs(max, n, i+1, d, sum+stick[i])) {
return 1;
}
}
visit[i] = 0;
if (!sum) {
return 0;
}
}
return 0;
}
int main()
{
int N, M, sum;
while (~scanf("%d",&N)) {
while (N --) {
scanf("%d",&M);
sum = 0;
for (int i = 0; i < M; ++ i) {
scanf("%d",&stick[i]);
sum += stick[i];
visit[i] = 0;
}
if (sum%4 || stick[0] > sum/4) {
puts("no");
}else {
sort(stick, stick+M, cmp);
if (dfs(sum/4, M, 0, 0, 0)) {
puts("yes");
}else {
puts("no");
}
}
}
}
return 0;
}
https://amrfeldfrawy.wordpress.com/2013/07/11/uva-10364-square/
http://naivered.github.io/2016/04/04/Problem_Solving/UVa/UVa-10364-Square/
https://blog.csdn.net/ljqmiao_/article/details/81201909
https://www.luogu.org/problemnew/solution/UVA10364
https://uva.onlinejudge.org/external/103/10364.pdf
http://luckycat.kshs.kh.edu.tw/homework/q10364.htm
給你一些棍子的長度，請你算出這些棍子是否可以連成一個正方形（端點對端點，且棍子不可折斷）
Input
輸入的第一列有一個整數N，代表以下有幾組測試資料。每組測試資料一列，第一個整數為M（4 <= M <= 20），代表棍子的數目。接下來的M個整數分別代表這M根棍子的長度，每支棍子的長度介於1到10000之間。
Output
對每一組測試資料，如果這些棍子可以連成一個正方形，輸出 yes。否則輸出 no。
Sample Input
5 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 8 1 7 2 6 4 4 3 9 8 1 7 2 6 4 4 3 13
Sample Output
yes no yes yes nohttps://github.com/wilson100hong/UVAOJ/blob/master/Volume_103/10364/square.cpp
// I solve this problem by DP with bitmask. Each bitmask denotes a set of
// "used" sticks (1 is used, 0 is not). Bitmask 10011 maps to a subset of
// sticks like {31, 24, 17}. (sticks[0] = 31, sticks[1] = 24, sticks[4] = 17).
//
// For each bitmask B, dp[B] stores the max number of groups the
// bitmask can be divided, where each group has sum equals to square's side
// lenght. Side length is calculated by sitcks_sum / 4. In the essence, dp[B]
// stores the max number of sides that B can formed for square.
//
// For example. sticks_sum = 20, side_length = 5 (20 / 4).
// For a bitmask maps to sticks {2, 3, 4, 5, 6}, we can optimally group sticks into
// 2 groups with sum == 5 ({2,3} and {5}), with 4 and 6 not grouped . We name
// the sum of ungrouped sticks "residue". In this case, the residue is 10 (4 +
// 6). It can be observed that if residue > side_length, then it is impossible
// to form square for B.
//
// Lets define sub-bitmask. For bitmask B, sub-bitmask B' is a bitmask deduced
// by flipping any bit in B which is 1 to 0. The number of B' sub-bitmasks
// equals to the number of "1"s in B.
//
// Finally, the dp induction:
// dp[B] = max(dp[B'] + 1 : if residue of B = edge /
// dp[B'] : if residue of B still < edge,
// 0 : if residue of B > edga,
// for all B's sub-bitmask B')
//
// natural ordering to scan B is good for us, since we will meet every B' before B.
//
// Most important, we need some optimizations:
// 1. only need to try half of mask -- we can assume stick[m - 1] is always not used.
// 2. dont precompute anything for all bitmask -- no in dp[], no in value[].
// But vector initalization is fine.
int get_bit(int n, int bit) {
return (n & (1 << bit)) >> bit;
}
// DEBUG usage
string mask_str(int mask, int m) {
stringstream ss;
for (int bit = m - 1; bit >= 0; --bit) {
ss << get_bit(mask, bit);
}
return ss.str();
}
bool solve(vector<int>& sticks) {
sort(sticks.begin(), sticks.end());
reverse(sticks.begin(), sticks.end());
int sum = 0;
for (int stick : sticks) {
sum += stick;
}
if (sum % 4 != 0) return false;
int edge = sum / 4;
for (int stick : sticks) {
if (stick > edge)
return false;
}
int m = sticks.size();
int max = 1 << m;
vector<int> dp(max, 0);
vector<int> value(max, 0);
vector<int> res(max, 0);
int opt_div = 2;
for (int mask = 0; mask < max / 2; ++mask) { // Optimization: only need to do half
for (int bit = 0; bit < m; ++bit) {
if (get_bit(mask, bit)) {
value[mask] += sticks[bit];
}
}
for (int bit = 0; bit < m; ++bit) {
int d = 0;
int p_mask = mask ^ (1 << bit); // set mask i-bit to 0
if (mask & (1 << bit) && res[p_mask] <= edge) {
int res = value[mask] - dp[p_mask] * edge;
if (res == edge) {
d = dp[p_mask] + 1;
} else if (res < edge) {
d = dp[p_mask];
}
}
if (d == 3) {
return true;
}
if (dp[mask] < d) {
dp[mask] = d;
res[mask] = value[mask] - dp[mask] * edge;
}
}
}
return false;
}
http://wilson100hong.blogspot.com/2015/05/uva-10364-square-dp-solution.html
We can view each bitmask as a set of "used" sticks (bit = 1 is used, 0 is not). So, bitmask "10011" means a subset of sticks {sticks[0], sticks[1], sticks[4]}.
Here comes the meaty DP part: for each bitmask B, we store:
1. value[B] : which is the sum of used sticks' length in B.
2. dp[B] : the max number of "edges" that B can achieve as part of a square. Each edge is formed by a set of sticks, with sum equals to square's side length. edge (= sum(sticks) / 4).
Let's use an example to see the meaning dp[]. Say sum(sticks) = 20, so
edge = 5. For a bitmask B meaning sticks with length {2, 3, 4, 5, 6}, we can group into 2 edges: {2,3} and {5}, with 4 and 6 remaining not grouped. We name the sum of such ungrouped sticks "residue". In this example, the residue is 10 (4 + 6).
You can observe that when a residue of B > edge, it is possible to form a square starting from B by adding more sticks.
If we flip any bit which is '1' in B to '0', we will get another bitmask B'. A bitmaks B could have multiple such flipped bitmask, as the number of '1' in B. Lets called all this flipped bitmasks "child-bitmask". The index of flipped bit is "flipped-bit" fb', it connects to a stick[fb']
The main idea of DP solution is, for every B, we try all its child bitmask B', to see what is the best dp[B] we can get by adding stick[fb']. This will needs to refer dp[B'] and residue[B'], lets list different cases:
Do this for all B' of B:
1. residue[B'] > edge :
There is no way to construct a square by adding sticks in B', Prune it!
2. If residue[B'] == edge :
This never happens (think about it!)
3. If residue[B'] < edge :
use temp variables new_dp, new_res
There could another three possibilities:
a. residue[B'] + stick[fb'] < edge:
new_dp = dp[B'], new_res = residue[B'] + stick[fb']
b. residue[B'] + stick[fb'] == edge:
new_dp = dp[B'] + 1, new_res = 0
c. residue[B'] + stick[fb'] > edge:
Same as 1. Prune it!
Finally, pick the max new_dp in B' for dp[B], and use the corresponding new_res in residue[B].
In implementation, we can scan the DP array for all B by nature ordering (0000, 0001, 0010, ...1111), since every child bitmask B' will be encountered before its parent B. (think about it!)
In order to get AC, some optimization tips:
1. We only need to try half of all bitmask -- we can always assume stick[m -1] is not used, because of symmetry (think about it!)
2. Don't precompute for whole bitmask -- this prohibits any potential pruning, and will get you TLE.
I used a bitmasking technique coupled with a dynamic programming technique to come up with an solution.
First of all, let a[i] be the length of i-th stick, and let's define as a bit mask containing N bits which indicates that i-th stick is included in b if b[i] equals to 1, and 0 otherwise. We can first precompute val[b], the sum of all a[i] for which b[i] is set to 1. Furthermore, let's define X be the sum of all a[i] divided by 4. As you can guess, X is the length of each sides of the resulting square in the end. Let D[b] be the number of times we passed a multiple of X. D[b] = k will mean that we can divide N sticks into k groups of total length X each, and possibly one more group with total length less than X. Therefore we have the following relationship:
let K = max { D[b with j-th bit set to 0] }, then
D[b] = K + { 1 if val[b] equals to (K+1)X, and 0 otherwise }
In the end, we will have D[-1] = 4 if and only if there exists a possible partitioning of the sticks into 4 groups of total length X.
To pass the UVa time limit, you need to make use of a symmetry: since every stick must belong to a group, we can without loss of generality set the first stick to be in the first group and proceed as per usual. This optimisation alone will reduce the search time by half.
int dp[1<<20]; int val[1<<20]; int a[23]; int N; void solve() { for(int b=0, sz=(1<<N);b<sz;++b){ val[b] = -1; dp[b] = 0; } int sum = 0; val[0] = 0; for(int i=0;i<N;++i){ sum += a[i]; val[1<<i] = a[i]; } int X = sum/4; if(sum % 4 != 0) { printf("no\n"); return; } for(int b=0, sz=(1<<N);b<sz;++b){ if(val[b] != -1) continue; int msb = b & (-b); val[b] = val[msb] + val[b ^ msb]; } for(int b=0, sz=(1<<(N-1));b<sz;++b){ int bm = (b << 1) | 1; for(int i=0;i<N-1;++i){ if(b & (1<<i)) { dp[b] = max(dp[b], dp[b ^ (1<<i)]); } } if(val[bm] == (dp[b]+1) * X) dp[b]++; } if(dp[(1<<(N-1))-1] == 4) { printf("yes\n"); } else { printf("no\n"); } }X. DFS
https://blog.csdn.net/mobius_strip/article/details/51834170
剪枝：1.排序，預處理；
2.如果相同長度前面的沒選，後面的不會選；
3.如果發現構造一根長棍子失敗，則不會成功；
4.在構造一根長棍子時，按照順序取小棍子；
int dfs(int max, int n, int s, int d, int sum)
{
if (d == 3) {
return 1;
}
for (int i = s; i < n; ++ i) {
if (visit[i] || i && !visit[i-1] && stick[i] == stick[i-1]) {
continue;
}
visit[i] = 1;
if (sum + stick[i] == max) {
if (dfs(max, n, 0, d+1, 0)) {
return 1;
}
}else if (sum + stick[i] < max) {
if (dfs(max, n, i+1, d, sum+stick[i])) {
return 1;
}
}
visit[i] = 0;
if (!sum) {
return 0;
}
}
return 0;
}
int main()
{
int N, M, sum;
while (~scanf("%d",&N)) {
while (N --) {
scanf("%d",&M);
sum = 0;
for (int i = 0; i < M; ++ i) {
scanf("%d",&stick[i]);
sum += stick[i];
visit[i] = 0;
}
if (sum%4 || stick[0] > sum/4) {
puts("no");
}else {
sort(stick, stick+M, cmp);
if (dfs(sum/4, M, 0, 0, 0)) {
puts("yes");
}else {
puts("no");
}
}
}
}
return 0;
}
https://amrfeldfrawy.wordpress.com/2013/07/11/uva-10364-square/
lets solve the problem by finding 4 sets has same sum and the total sum is divisible by 4
there is a nice recurrence you can find when looking to the problem as find One subset {not four} has sum k and mark the elements that you have chosen to build this subset ,
there is a nice recurrence you can find when looking to the problem as find One subset {not four} has sum k and mark the elements that you have chosen to build this subset ,
so if we have 8 elements {1,2,1,2,1,2,1,2} and we want to build a subset has sum==(k)== 3 ,
at the end we will have visited {1, 1 ,0,0,0,0,0,0 } ,
you Can now add another parameter (number of subsets ) to solve the big problem
and change the( return 1 ) to return Canmake(0,numberofsets-1,k), which means that we have One subset has sum == k so lets find the remaining 3 subsets
at the end we will have visited {1, 1 ,0,0,0,0,0,0 } ,
you Can now add another parameter (number of subsets ) to solve the big problem
and change the( return 1 ) to return Canmake(0,numberofsets-1,k), which means that we have One subset has sum == k so lets find the remaining 3 subsets
int sticks[25];bool visited [25];int k;int m,l;int sum;bool Canmake(int index, int numberofsets, int sum){ if(numberofsets==0) return 1; else if(sum==0) //we have found one subset so lets find the remaking return Canmake(0,numberofsets-1,k); else if(sum<0|| index == m || numberofsets <0) return 0; else { if(sum>=sticks[index]&& !visited [index]) { visited [index]=1; if(Canmake(index +1 , numberofsets , sum - sticks[index])) return 1; visited [index]=0; } if(Canmake(index +1 , numberofsets , sum) ) return 1; } return 0;} while(n--) { sum=0; scanf("%d",&m); for(int i=0; i<m; i++) { scanf("%d",&l); sum+=l; sticks[i]=l; } if(sum%4!=0) printf("no\n"); else { k=sum/4; memset(visited ,0,sizeof visited ); if(Canmake(0,4,k)) printf("yes\n"); else printf("no\n"); } }http://naivered.github.io/2016/04/04/Problem_Solving/UVa/UVa-10364-Square/
一開始先排序由長的棍子開始組，可以減少回溯次數。
計算出正方形單邊的長度後，回溯時，只要長度超過單邊就可以不用進行遞迴了。每完成一個邊就將長度歸 0 ，重新開始組另一邊(只需要完成 3 個邊就可以確定了)，一方面紀錄使用了那些棍子。
計算出正方形單邊的長度後，回溯時，只要長度超過單邊就可以不用進行遞迴了。每完成一個邊就將長度歸 0 ，重新開始組另一邊(只需要完成 3 個邊就可以確定了)，一方面紀錄使用了那些棍子。
int side_length;//單邊長度 int stick[21]; bool used[21]; bool backtracking(int n, int len, int now, int idx); int main() { int Case; scanf("%d", &Case); while (Case--) { int n, sum = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &stick[i]); sum += stick[i]; } //先排序減少回溯次數 sort(stick, stick + n, [](const int& s1, const int& s2)->bool{return s1 > s2; }); fill(used, used + n, false); side_length = sum / 4;//單邊長度 if (sum % 4 || stick[0] > side_length) puts("no"); else puts(backtracking(n, 0, 0, 0) ? "yes" : "no"); } return 0; } bool backtracking(int n, int len, int now, int idx)//(棍子數,目前連接的長度,完成的邊數,紀錄做到哪根棍子) { //完成一邊 if (len == side_length) { len = idx = 0; now++; if (now == 3) return true; } for (int i = idx; i < n; i++) { if (!used[i]) { if (len + stick[i] <= side_length)//提早排除長度超過的 { used[i] = true; if (backtracking(n, len + stick[i], now, i + 1)) return true; used[i] = false; //待會就算用別根完成了現在這一邊，最後還是有邊無法完成 if (len + stick[i] == side_length) return false; } } } return false; }
https://blog.csdn.net/ljqmiao_/article/details/81201909
https://www.luogu.org/problemnew/solution/UVA10364
int m,l,a[25];
bool su[25];//标记有没有选
int dfs(int pos,int len,int b){
if(b==3) return 1;//如果都构成3边了，那么最后一遍是肯定构成的
for(int i=pos;i>=0;i--){
if(!su[i]){//没走过
su[i]=1;//置为走过
if(len+a[i]<l){//长度小于边长
if(dfs(i-1,len+a[i],b)) return 1;
}
else{
if(len+a[i]==l)//正好等于边长
if(dfs(m-1,0,b+1)) return 1;//边数加1
}
su[i]=0;//归为未走
}
}
return 0;
}
int main()
{
int i,t,sum,maxn;
scanf("%d",&t);
while(t--){
sum=0;
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d",&a[i]);//读入
sum+=a[i];//算出木棍长度的总和
}
l=sum/4;//算出边长
memset(su,0,sizeof(su));
sort(a,a+m);
if(l*4!=sum||m<4||l<a[m-1]) printf("no\n");//如果不能构成正方形或边长小于最大值
else if(dfs(m-1,0,0)) printf("yes\n");//DFS
else printf("no\n");//输出完毕
}
return 0;
}