在给定条件下将 N 件物品分发给三个人的方法数

Question

我一直在尝试解决一个问题，确定将 N 件物品分发给三个人的方法数。如果第一个人得到的物品的总重量能被 3 整除，第二个人得到的物品重量能被 5 整除，最后一个人得到的物品总重量能被 7 整除 &每个人得到的物品不应该是0。

第一个输入 N 被认为是项目的数量，第二行输入表示 N 个代表项目权重的整数。第 i 个整数 a[i] 表示第 i 个项目的权重。有这样的限制，

3≤ N ≤12
1≤ a[i] ≤10^10

sample input 1:
6
2 3 5 7 9 13

sample output 1:
6

我尝试了一种解决问题的方法，但无法弄清楚该解决方案如何更好，以便第一、第二和第三人收到的物品重量可以被 3、5 & 整除分别为 7 个。我尝试让一个人在三个人中获得最大数量的物品并且每个人至少获得一件物品，但无法找出每个人获得的物品总重量可以被 3 整除的“最佳”解决方案, 5 & 7 分别。您能否建议DP中的解决方案来解决所有测试用例中的问题？

这是我在三个人之间进行简单分配的解决方案。 TIA.

#include<bits/stdc++.h>
using namespace std;

int countWays(int N)
{
    int ans = ((N-1)*(N-2))/2;

    //storing the number of distribution that is not possible
    int s = 0;

    for(int i=2; i<=N-3; i++){
        for(int j=1; j<i; j++){
            //possibilities of 2 persons receiving the maximum
            if (N == 2 * i + j)
                s++;
        }
    }

    if(N%3 == 0)
        s = 3*s+1;
    else
        s = 3*s;

    //final ways to distribute
    return ans - s;
}

int main()
{
    int n, N=0;
    cin >> n;

    if(n<3 && n>12)
        return 0;

    vector<int> a(n);

    for(int i=0; i<n; i++){
        cin>>a[i];
        N += a[i];
    }

    cout<<countWays(N);

    return 0;
}

Answer 1

对于如此小的项目编号，您可以生成所有项目分布 (3^12~~531000) 并检查条件。

int countWays(int n, int* arr, int aa = 0, int bb = 0, int cc = 0) {
    if (n < 0) {
        return (aa*bb*cc > 0 && (aa % 3) == 0 && (bb % 5) == 0 && (cc % 7) == 0) ? 1 : 0;
    }
    return countWays(n - 1, arr, aa + arr[n], bb, cc) +
           countWays(n - 1, arr, aa, bb + arr[n], cc) +
           countWays(n - 1, arr, aa, bb, cc + arr[n]);
}

int main()
{
    int n = 6;
    int a[6] = { 2, 3, 5, 7, 9, 13 };

    std::cout << countWays(n-1, a);
}

打印6

对于更大的项目数量，也许值得使用带记忆的动态编程。

Answer 2

你需要的动态规划状态是三个标志，分别表示 1、2 和 3 人是否收到了任何东西，后面跟着 3 个数字，给出了他们收到的东西的总和 mod 3、5 和7.

在 Python 中，我将构建一个字典，其键是表示状态的元组，其值是计数。在 C++ 中，您可能更喜欢将状态表示为一个整数（每个值都由特定位编码）和一个数组来表示查找。无论哪种方式，你从一端开始计数 1 因为没有人收到任何东西，处理每个项目并跟踪计数以了解如何将它们提供给每个人，并在另一端查找每个人收到的计数总数为 0.

这是一个 Python 解决方案，您可以验证它是否合理。

def divisions (item_weights):
    count_by_state = {(False, 0, False, 0, False, 0): 1}
    for weight in item_weights:
        next_count_by_state = {}

        for state, count in count_by_state.items():
            # Each variable is pX_Y where
            #   X is the person
            #   Y is either r for whether they [r]eceived or w for [w]eight.
            p1_r, p1_w, p2_g, p2_w, p3_g, p3_w= state
            for next_state in [
                (True, (p1_w + weight)%3, p2_g, p2_w, p3_g, p3_w),
                (p1_r, p1_w, True, (p2_w + weight)%5, p3_g, p3_w),
                (p1_r, p1_w, p2_g, p2_w, True, (p3_w + weight)%7),
                ]:
                if next_state in next_count_by_state:
                    next_count_by_state[next_state] += count
                else:
                    next_count_by_state[next_state] = count

        count_by_state = next_count_by_state
    return count_by_state[(True, 0, True, 0, True, 0)]

print(divisions([2, 3, 5, 7, 9, 13]))

请注意，通过更多的工作，我实际上可以按字典顺序打印解决方案。有了更多，我可能会被要求打印第 500 个并只打印那个。然而，这是我研究出的一个动态编程技巧，none 这些比赛似乎认为很重要。

在给定条件下将 N 件物品分发给三个人的方法数

Number of ways to distribute N items to three peoples under given conditions

c++

algorithm

dynamic-programming

c++11