c++ - Coursera DSA 算法工具箱第 4 周第 2 题

问题描述

问题陈述-您和您的两个朋友在访问了多个国家后刚刚回到家中。现在你想平分你们三个人买的所有纪念品。

问题描述输入格式 - 第一行包含一个整数...第二行包含整数 v1, v2, 。. . ,vn 以空格分隔。

约束 - 1。... 20, 1 . ...... 全部30...

输出格式 - 输出 1，如果可以分区 1、2、. . . , 分成三个总和相等的子集，否则为 0。

这个解决方案有什么问题？当我提交时我得到了错误的答案（#12/75）我正在使用背包解决它而没有重复以 SUm/3 作为我的体重。我回溯我的解决方案，用 0 替换它们。测试用例在我的 PC 上正确运行。虽然我是用 OR 逻辑做的，取了一个布尔数组，但是 IDK 这个有什么问题？

示例- 11

17 59 34 57 17 23 67 1 18 2 59

(67 34 17) 被替换为 0。这样它们就不会干扰下一个元素总和（18 1 23 17 59）。因为它们都等于 118(sum/3) 打印 1。

#include <iostream>
#include <vector>

using namespace std;
int partition3(vector<int> &w, int W)
{
        int N = w.size();

//using DP to find out the sum/3 that acts as the Weight for a Knapsack problem
        vector<vector<int>> arr(N + 1, vector<int>(W + 1));
        for (int k = 0; k <= 1; k++)
        {
//This loop runs twice coz if 2x I get sum/3 then that ensures that left elements will make up sum/3 too
                for (int i = 0; i < N + 1; i++)
                {
                        for (int j = 0; j < W + 1; j++)
                        {
                                if (i == 0 || j == 0)
                                        arr[i][j] = 0;
                                else if (w[i - 1] <= j)
                                {
                                        arr[i][j] = ((arr[i - 1][j] > (arr[i - 1][j - w[i - 1]] + w[i - 1])) ? arr[i - 1][j] : (arr[i - 1][j - w[i - 1]] + w[i - 1]));
                                }
                                else
                                {
                                        arr[i][j] = arr[i - 1][j];
                                }
                        }
                }

                if (arr[N][W] != W)
                        return 0;
                else
                {
//backtrack the elements that make the sum/3 and = them to 0 so that they don't contribute to the next //elements that make sum/3
                        int res = arr[N][W];
                        int wt = W;
                        for (int i = N; i > 0 && res > 0; i--)
                        {
                                if (res == arr[i - 1][wt])
                                        continue;
                                else
                                {
                                        std::cout << w[i - 1] << " ";
                                        res = res - w[i - 1];
                                        wt = wt - w[i - 1];
                                        w[i - 1] = 0;
                                }
                        }
                }
        }
        if (arr[N][W] == W)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

int main()
{
        int n;
        std::cin >> n;
        vector<int> A(n);
        int sum = 0;
        for (size_t i = 0; i < A.size(); ++i)
        {
                int k;
                std::cin >> k;
                A[i] = k;
                sum += k;
        }
        if (sum % 3 == 0)
                std::cout << partition3(A, sum / 3) << '\n';
        else
                std::cout << 0;
}

标签： c++algorithmpartitioningknapsack-problemdsa

c++ - Coursera DSA 算法工具箱第 4 周第 2 题 - 分区纪念品

问题描述

解决方案

推荐阅读