Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) a
Posted: Thu May 05, 2022 12:48 pm
Suppose n people live in a house and wish to share their
expenses equally. Their respective expenses (before settling) are
x1, ..., xn. They agree to make payments to each other so as to
make all their net expenses equal. Naturally, they want to make a
few payments as possible
2. Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are ₁,..., n. They agree to make payments to each other so as to make all their net expenses equal. Naturally, they want to make a few payments as possible. BALANCE denotes the decision version of this problem: Given nonnegative integers ₁,...,n (written in binary) and an integer k, can the net expenses be balanced using k or fewer payments? a) Show that BALANCE belongs to NP. b) Show that SUBSET SUM ≤, BALANCE, and thereby conclude that BALANCE is NP-complete.
expenses equally. Their respective expenses (before settling) are
x1, ..., xn. They agree to make payments to each other so as to
make all their net expenses equal. Naturally, they want to make a
few payments as possible
- Suppose N People Live In A House And Wish To Share Their Expenses Equally Their Respective Expenses Before Settling A 1 (57.81 KiB) Viewed 37 times