Subset sum problem: Difference between revisions
Content added Content deleted
(Added Java) |
|||
Line 852: | Line 852: | ||
(One of those is the empty solution, but the rest of them are valid.) |
(One of those is the empty solution, but the rest of them are valid.) |
||
=={{header|Java}}== |
|||
{{trans|Kotlin}} |
|||
<lang Java>public class SubsetSum { |
|||
private static class Item { |
|||
private String word; |
|||
private int weight; |
|||
public Item(String word, int weight) { |
|||
this.word = word; |
|||
this.weight = weight; |
|||
} |
|||
@Override |
|||
public String toString() { |
|||
return String.format("(%s, %d)", word, weight); |
|||
} |
|||
} |
|||
private static Item[] items = new Item[]{ |
|||
new Item("alliance", -624), |
|||
new Item("archbishop", -915), |
|||
new Item("balm", 397), |
|||
new Item("bonnet", 452), |
|||
new Item("brute", 870), |
|||
new Item("centipede", -658), |
|||
new Item("cobol", 362), |
|||
new Item("covariate", 590), |
|||
new Item("departure", 952), |
|||
new Item("deploy", 44), |
|||
new Item("diophantine", 645), |
|||
new Item("efferent", 54), |
|||
new Item("elysee", -326), |
|||
new Item("eradicate", 376), |
|||
new Item("escritoire", 856), |
|||
new Item("exorcism", -983), |
|||
new Item("fiat", 170), |
|||
new Item("filmy", -874), |
|||
new Item("flatworm", 503), |
|||
new Item("gestapo", 915), |
|||
new Item("infra", -847), |
|||
new Item("isis", -982), |
|||
new Item("lindholm", 999), |
|||
new Item("markham", 475), |
|||
new Item("mincemeat", -880), |
|||
new Item("moresby", 756), |
|||
new Item("mycenae", 183), |
|||
new Item("plugging", -266), |
|||
new Item("smokescreen", 423), |
|||
new Item("speakeasy", -745), |
|||
new Item("vein", 813), |
|||
}; |
|||
private static final int n = items.length; |
|||
private static final int[] indices = new int[n]; |
|||
private static int count = 0; |
|||
private static final int LIMIT = 5; |
|||
private static void zeroSum(int i, int w) { |
|||
if (i != 0 && w == 0) { |
|||
for (int j = 0; j < i; ++j) { |
|||
System.out.printf("%s ", items[indices[j]]); |
|||
} |
|||
System.out.println("\n"); |
|||
if (count < LIMIT) count++; |
|||
else return; |
|||
} |
|||
int k = (i != 0) ? indices[i - 1] + 1 : 0; |
|||
for (int j = k; j < n; ++j) { |
|||
indices[i] = j; |
|||
zeroSum(i + 1, w + items[j].weight); |
|||
if (count == LIMIT) return; |
|||
} |
|||
} |
|||
public static void main(String[] args) { |
|||
System.out.printf("The weights of the following %d subsets add up to zero:\n\n", LIMIT); |
|||
zeroSum(0, 0); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>The weights of the following 5 subsets add up to zero: |
|||
(alliance, -624) (archbishop, -915) (balm, 397) (bonnet, 452) (brute, 870) (centipede, -658) (cobol, 362) (covariate, 590) (departure, 952) (deploy, 44) (diophantine, 645) (efferent, 54) (elysee, -326) (eradicate, 376) (escritoire, 856) (exorcism, -983) (fiat, 170) (filmy, -874) (flatworm, 503) (mincemeat, -880) (plugging, -266) (speakeasy, -745) |
|||
(alliance, -624) (archbishop, -915) (balm, 397) (bonnet, 452) (brute, 870) (centipede, -658) (cobol, 362) (covariate, 590) (departure, 952) (deploy, 44) (diophantine, 645) (efferent, 54) (elysee, -326) (eradicate, 376) (escritoire, 856) (exorcism, -983) (infra, -847) (isis, -982) (mincemeat, -880) (moresby, 756) (mycenae, 183) (smokescreen, 423) (speakeasy, -745) |
|||
(alliance, -624) (archbishop, -915) (balm, 397) (bonnet, 452) (brute, 870) (centipede, -658) (cobol, 362) (covariate, 590) (departure, 952) (deploy, 44) (diophantine, 645) (efferent, 54) (elysee, -326) (eradicate, 376) (escritoire, 856) (fiat, 170) (infra, -847) (isis, -982) (markham, 475) (mincemeat, -880) (plugging, -266) (speakeasy, -745) |
|||
(alliance, -624) (archbishop, -915) (balm, 397) (bonnet, 452) (brute, 870) (centipede, -658) (cobol, 362) (covariate, 590) (departure, 952) (deploy, 44) (diophantine, 645) (efferent, 54) (elysee, -326) (eradicate, 376) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (mincemeat, -880) (moresby, 756) (plugging, -266) (vein, 813) |
|||
(alliance, -624) (archbishop, -915) (balm, 397) (bonnet, 452) (brute, 870) (centipede, -658) (cobol, 362) (covariate, 590) (departure, 952) (deploy, 44) (diophantine, 645) (efferent, 54) (elysee, -326) (eradicate, 376) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (smokescreen, 423)</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |