Разработать алгоритм

Question

Я участвовал в соревновании по программированию в моем университете. Я решил все вопросы, кроме этого. Сейчас я практикую этот вопрос, чтобы улучшить свои навыки. Но я не могу понять алгоритм. Если есть какой-либо алгоритм, пожалуйста, обновите меня. Или любой подобный алгоритм присутствует, тогда, пожалуйста, скажите мне, что я изменю его в соответствии с этим вопросом.

Это то, что я хочу сделать.

• Первая строка ввода - это расстояние между двумя точками.
• После этого каждая последующая строка содержит пару цифр, указывающих длину кабеля и количество этого кабеля. Эти кабели используются для соединения двух точек.
• Ввод завершается 0 0

Выход:

• Выход должен содержать одно целое число, представляющее Минимальное количество стыков возможно для построения требуемой длины канатной дороги. Если решение невозможно, напечатайте «Нет решения».

Пример ввода

444
16 2
3 2
2 2
30 3
50 10
45 12
8 12
0 0

Пример вывода

10

Answer 1

Спасибо, ребята. Я нашел решение проблемы «Идеальная сумма подмножеств», а затем внес в нее несколько изменений. Вот код.

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

bool dp[100][100];
int sizeOfJoints = -1;
void display(const vector<int>& v)
{
    if (sizeOfJoints == -1)
    {
        sizeOfJoints = v.size() - 1;
    }

    else if (v.size()< sizeOfJoints)
    {
        sizeOfJoints = v.size() - 1;
    }
}

// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
void printSubsetsRec(int arr[], int i, int sum, vector<int>& p)
{

    // If sum becomes 0
    if (sum == 0)
    {
        display(p);
        return;
    }

    if(i<=0 || sum<0)
        return;

    // If given sum can be achieved after ignoring
    // current element.
    if (dp[i-1][sum])
    {
        // Create a new vector to store path
        //vector<int> b = p;
        printSubsetsRec(arr, i-1, sum, p);
    }

    // If given sum can be achieved after considering
    // current element.
    if (sum >= arr[i-1] && dp[i-1][sum-arr[i-1]])
    {
        p.push_back(arr[i-1]);
        printSubsetsRec(arr, i-1, sum-arr[i-1], p);
        p.pop_back();
    }
}

// all subsets of arr[0..n-1] with sum 0.
void printAllSubsets(int arr[], int n, int sum)
{
    if (n == 0 || sum < 0)
        return;

    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= sum; i++)
        dp[0][i] = false;

    // Fill the subset table in botton up manner
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
            if(j<arr[i-1])
                dp[i][j] = dp[i-1][j];
            if (j >= arr[i-1])
                dp[i][j] = dp[i-1][j] ||
                           dp[i - 1][j-arr[i-1]];
        }
    }

    if (dp[n][sum] == false)
    {

        return;
    }

    // Now recursively traverse dp[][] to find all
    // paths from dp[n-1][sum]
    vector<int> p;
    printSubsetsRec(arr, n, sum, p);
}

// Driver code
int main()
{



    int input[2000];
    int inputIndex = 0;
    int i = 0;
    int distance = 0;

    cout<< "Enter Input: " <<endl;
    cin>> distance;
    while(true)
    {
        int temp1 = 0;
        int temp2 = 0;
        cin>> temp1;
        cin>> temp2;
        if (temp1 == 0 && temp2 == 0)
        {
            break;
        }

        for (i = 0; i < temp2; i++)
            input[inputIndex++] = temp1;
    }
    cout<< "Processing output. Please wait: " <<endl;
    printAllSubsets(input, inputIndex, distance);
    if(sizeOfJoints != -1)
        cout<<sizeOfJoints;
    else
        cout<<"No Solution Possible";
    return 0;
}