1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
package scratch;
import java.util.Arrays;
public class TestBalance {
static long complexity=0;
static int[] L1 = new int[] { 7991,6765,2584,987,377,144,55,21,8,3,1 };
static int[] L2 = new int[] { 10946,4181,1597,610,233,89,34,13,5,2 };
/**
* Check if a given weight can be reach using a given list of masses
*
* @param target weight to reach
* @param L list of masses
* @param start starting index for enumerating the list (recursive call)
* @param max sum of masses with index>start
* @return true if the given weight can be reach, otherwise false
*/
static boolean isPossible(int target, int[] L, int max, int start) {
for(int i=start;i<L.length;i++) {
complexity++;
// target out of reach -> exit
if (target>max) break;
// IMPORTANT: take the next mass from high to low
int w = L[L.length-i-1];
// remaining sum of weights
max-=w;
// found exact match -> SUCCESS !
if (target==w) return true;
// mass is to high, so don't use it -> next
if (w>target) continue;
// use the current mass and check the rest
if (isPossible(target-w, L, max, i+1)) return true;
}
// no match found -> FAIL !
return false;
}
public static void main(String[] args) {
// sorting L1
Arrays.sort(L1);
complexity+=(int)L1.length*Math.log(L1.length);
// sorting L2
Arrays.sort(L2);
complexity+=(int)L2.length*Math.log(L2.length);
// min/max possible weights using L1
int minL1=L1[0],maxL1=0;
for(int i=0;i<L1.length;i++) {
complexity++;
if (L1[i]<minL1) minL1=L1[i];
maxL1+=L1[i];
}
// min/max possible weights using L2
int minL2=L2[0],maxL2=0;
for(int i=0;i<L2.length;i++) {
complexity++;
if (L2[i]<minL2) minL2=L2[i];
maxL2+=L2[i];
}
// min/max possible weights of equilibrium
int maxPossible=Math.min(maxL1,maxL2);
int minPossible=Math.max(minL1,minL2);
for(int target=maxPossible;target>=minPossible;target--)
if (isPossible(target, L1, maxL1, 0))
if (isPossible(target, L2, maxL2, 0))
{System.out.println("Winner is: "+target); break;}
System.out.println("operations: "+complexity);
}
} |
Equilibrage balance à plateaux : approche mathématique ?
Répondre avec citation
Envoyé par Trap D
)
pour vos réponses.
). Et c'est pas en Cnm..
), mais je ne vois pas autre chose.
), soit moins que la version optimisée. J'ai du me gourer quelquepart. 
(ou pas)
Partager