Минимальное количество предметов в рюкзаке, для точного соответствия заданному весу

@TinyColonel · Регистрация: 19.10.2019

Author24 — интернет-сервис помощи студентам

Здравствуйте, решал задачи с рюкзаком и наткнулся на следующую:

Код

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

Входные данные:
Первая строка входных данных содержит натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.
Во второй строке находится N натуральных чисел mi, не превышающих 100.

Выходные данные:
Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

В голову пришло только сделать обычный рюкзак, где вес предмета равен его цене. И потом восстанавливать ответ, для каждой вершины с весом M и находить минимальную длину ответа. Но часть тестов не проходит с WA. Мой код:

C++

#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<deque>
#include<utility>
#include<string>
#include<set>
#include<iterator>
#include<queue>
#include<cstring>
#include<stack>
#include<math.h>
#define ll long long
using namespace std;
const long long inf = (long long)1000000000000000111;
 
ll i, j, k = inf, f, n, m;
vector<ll> c, w, ans;
vector<vector<ll>> a;
 
void Way(ll i, ll j) {
    if (a[i][j] == 0) {
        return;
    }
    if (a[i - 1][j] == a[i][j]) {
        Way(i - 1, j);
    }
    else {
        Way(i - 1, j - w[i]);
        ans.push_back(i);
    }
}
 
int main() {
    cin >> n >> m;
    a.resize(n + 1, vector<ll>(m + 1, 0));
    c.resize(n + 1);
    w.resize(n + 1);
    for (i = 1; i <= n; i++) {
        cin >> w[i];
        c[i] = w[i];
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            a[i][j] = max(a[i - 1][j], a[i][j - 1]);
            if (w[i] <= j) {
                a[i][j] = max(a[i][j], a[i - 1][j - w[i]] + c[i]);
            }
        }
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i][j] == m) {
                ans.clear();
                Way(i, j);
                f = ans.size();
                k = min(k, f);
            }
        }
    }
    if (ans.size() == 0) {
        cout << 0;
        return 0;
    }
    cout << k;
}

Заранее спасибо.

@nalbe666 · 06.01.2021, 20:50

Это разновидность Subset sum problem, хоть и похожа на проблему рюкзака. Посмотрите, как выглядит код у geeksforgeeks и допилите под свои нужды. Матрицу они построили, осталось найти наименьший путь, с чем поможет bfs.

@LegionK · 07.01.2021, 09:22

Не ясно, в чем проблема хранить в a[i][j] не максимальную цену набранных предметов, как у вас сейчас в коде, а как раз наименьший размер подмножества. Вместо максимумов в 46, 48 выбирать минимумы, c[i] заменить на 1, вместо восстановления ответа вывести a[n][M]. И, если у вас сейчас рюкзак правильно написан, вроде как должно работать.

@nalbe666 817 / 504 / 211 Регистрация: 19.01.2019 Сообщений: 1,196
	06.01.2021, 20:50	2
	Это разновидность Subset sum problem, хоть и похожа на проблему рюкзака. Посмотрите, как выглядит код у geeksforgeeks и допилите под свои нужды. Матрицу они построили, осталось найти наименьший путь, с чем поможет bfs. 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	07.01.2021, 09:22	3
	Не ясно, в чем проблема хранить в a[i][j] не максимальную цену набранных предметов, как у вас сейчас в коде, а как раз наименьший размер подмножества. Вместо максимумов в 46, 48 выбирать минимумы, c[i] заменить на 1, вместо восстановления ответа вывести a[n][M]. И, если у вас сейчас рюкзак правильно написан, вроде как должно работать. 0

Опции темы