因此，您可以通过运行 max-flow lg（最大 N）次来解决第一个问题，使用二元斩波来找出最好的N 的可能值为。既然可以用最大流来求解，那么也可以用线性规划来求解。这样做，也许只是为了 N 的临界值，可能会让您比其他分配更喜欢某些分配，或者也许看看哪里有相邻的可行解决方案，然后看看是否可以混合它们以平等地使用类别。
示例 - 创建一个源，并将其链接到每个类别 Ci，链接的容量是该类别中可用表单的数量，因此 C1 从容量为 20 的源获取链接。使用其源的容量创建链接在用户和类别之间，用户有权访问该类别，因此 U1 可以获得指向 C1 和 C2 的链接，但 U2 只能获得指向 C2 的链接。现在创建从每个用户到单个接收器的容量为 N 的链接。如果向用户分配表单，为每个用户提供 N 个表单，那么这将产生填充从用户到接收器的每个链接的最大流量，并且您可以查看用户和类别之间的流量以了解如何分配表单。您可以从 N = 3 开始，因为用户 2 总共只能访问 3 个表单，因此答案不能大于此值。这是行不通的，因为你说过正确的答案是 N = 2，所以最大流量不会填满所有 N=3 的容量链路。所以你的程序在 3/2 = 1 处再次尝试，并找到一个解决方案 - 你已经为 N = 2 提供了一个解决方案，因此必须有一个 N = 1 的解决方案。现在程序知道有一个 N = 1 的解决方案，但是对于 N = 3 来说不是一个，因此它会在 N = (1 + 3) / 2 = 2 之间尝试一个，并找到您的解决方案。有一个适用于 N = 2 的解决方案，但不适用于 N = 3 的解决方案，因此 N = 2 的解决方案是您能做的最好的解决方案。
It seems to me that if you fix a number N of forms per user and ask the question: can we give N forms to each user? then you can turn this into a http://en.wikipedia.org/wiki/Maximum_flow_problem problem, where each user can receive flow/forms from their subset of categories, and there is an outflow of capacity N from each user. Also, if you can solve this problem for N you can solve it for all lesser values of N.
So you could solve the first problem by running max-flow lg (maximum N) times, using a binary chop to find out what the best possible value of N is. Since you can solve it by max flow, you can also solve it by linear programming. Doing it this way, perhaps just for the critical value of N, might allow you to favour some assignments over others, or perhaps to see where there are neighbouring feasible solutions, and then see if you can mix them to use categories equally.
Example - Create a source, and link it to each of the categories Ci, with the capacity of the link being the number of forms available in that category, so C1 gets a link from the source of capacity 20. Create links with their source's capacity between users and categories, where the user has access to the category, so U1 gets links to C1 and C2, but U2 only gets a link to C2. Now create links of capacity N from each user to a single sink. If there is an assignment of forms to users that gives every user N forms, then this will produce a maximum flow that fills every link from user to sink, and you can look at the flows between users and categories to see how to assign forms. You could start off with N = 3, because user 2 only has access to a total of 3 forms, so the answer can't be greater than that. That won't work because you have said the right answer has N = 2, so the max flow won't fill all the N=3 capacity links. So your program tries again at 3/2 = 1, and finds a solution - you have provided a solution for N = 2, so there must be one for N = 1. Now the program knows there is a solution for N = 1 but not one for N = 3 so it tries one halfway between at N = (1 + 3) / 2 = 2, and finds your solution. There is one for N = 2 but not for N = 3 so the N = 2 solution is the best you can do.
发布评论
评论（1）
在我看来，如果您为每个用户固定 N 个表单并提出问题：我们可以为每个用户提供 N 个表单吗？那么你可以把它变成一个 http://en.wikipedia.org/wiki/Maximum_flow_problem 问题，其中每个用户可以从其类别子集接收流/表单，并且每个用户都有容量 N 的流出。另外，如果您可以解决 N 的这个问题，您就可以解决 N 的所有较小值。
因此，您可以通过运行 max-flow lg（最大 N）次来解决第一个问题，使用二元斩波来找出最好的N 的可能值为。既然可以用最大流来求解，那么也可以用线性规划来求解。这样做，也许只是为了 N 的临界值，可能会让您比其他分配更喜欢某些分配，或者也许看看哪里有相邻的可行解决方案，然后看看是否可以混合它们以平等地使用类别。
示例 - 创建一个源，并将其链接到每个类别 Ci，链接的容量是该类别中可用表单的数量，因此 C1 从容量为 20 的源获取链接。使用其源的容量创建链接在用户和类别之间，用户有权访问该类别，因此 U1 可以获得指向 C1 和 C2 的链接，但 U2 只能获得指向 C2 的链接。现在创建从每个用户到单个接收器的容量为 N 的链接。如果向用户分配表单，为每个用户提供 N 个表单，那么这将产生填充从用户到接收器的每个链接的最大流量，并且您可以查看用户和类别之间的流量以了解如何分配表单。您可以从 N = 3 开始，因为用户 2 总共只能访问 3 个表单，因此答案不能大于此值。这是行不通的，因为你说过正确的答案是 N = 2，所以最大流量不会填满所有 N=3 的容量链路。所以你的程序在 3/2 = 1 处再次尝试，并找到一个解决方案 - 你已经为 N = 2 提供了一个解决方案，因此必须有一个 N = 1 的解决方案。现在程序知道有一个 N = 1 的解决方案，但是对于 N = 3 来说不是一个，因此它会在 N = (1 + 3) / 2 = 2 之间尝试一个，并找到您的解决方案。有一个适用于 N = 2 的解决方案，但不适用于 N = 3 的解决方案，因此 N = 2 的解决方案是您能做的最好的解决方案。
It seems to me that if you fix a number N of forms per user and ask the question: can we give N forms to each user? then you can turn this into a http://en.wikipedia.org/wiki/Maximum_flow_problem problem, where each user can receive flow/forms from their subset of categories, and there is an outflow of capacity N from each user. Also, if you can solve this problem for N you can solve it for all lesser values of N.
So you could solve the first problem by running max-flow lg (maximum N) times, using a binary chop to find out what the best possible value of N is. Since you can solve it by max flow, you can also solve it by linear programming. Doing it this way, perhaps just for the critical value of N, might allow you to favour some assignments over others, or perhaps to see where there are neighbouring feasible solutions, and then see if you can mix them to use categories equally.
Example - Create a source, and link it to each of the categories Ci, with the capacity of the link being the number of forms available in that category, so C1 gets a link from the source of capacity 20. Create links with their source's capacity between users and categories, where the user has access to the category, so U1 gets links to C1 and C2, but U2 only gets a link to C2. Now create links of capacity N from each user to a single sink. If there is an assignment of forms to users that gives every user N forms, then this will produce a maximum flow that fills every link from user to sink, and you can look at the flows between users and categories to see how to assign forms. You could start off with N = 3, because user 2 only has access to a total of 3 forms, so the answer can't be greater than that. That won't work because you have said the right answer has N = 2, so the max flow won't fill all the N=3 capacity links. So your program tries again at 3/2 = 1, and finds a solution - you have provided a solution for N = 2, so there must be one for N = 1. Now the program knows there is a solution for N = 1 but not one for N = 3 so it tries one halfway between at N = (1 + 3) / 2 = 2, and finds your solution. There is one for N = 2 but not for N = 3 so the N = 2 solution is the best you can do.