Возникли проблемы при реализации псевдокода для суммы подмножеств

Question

Возникли проблемы при реализации псевдокода для суммы подмножеств

поэтому я пытаюсь реализовать следующий псевдокод, но он не будет работать так, как предполагается. Вот описание проблемы на слайде: «Учитывая целочисленную границу« W »и набор из« n »элементов, каждый с положительным целым весом wi», найдите подмножество S элементов, которое: максимизирует Sigma sub i где i является элементом S «wi», сохраняя при этом эту сумму меньше или равной W. Я приложу следующие слайды, где я получаю описание проблемы и псевдокод. Проблема с моей реализацией состоит в том, что она будет только найти общее максимальное значение, а не значение, которое меньше или равно весу. Так, например, если бы у меня был Вес 10 (W = 10) и элементы 3 (n = 3) с весом элементов 1, 4, & 8 тогда следующий ответ должен быть 9; однако, мое решение дает 12. Вот слайды (* Пожалуйста, нет, где говорится, что w [j] это должно быть w [i] — у слайда была опечатка):

Вот мой код, который реализует псевдокод:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max(int a, int b, int c) {
if (a >= b)
return a;
else
return b;
}

int optimal_weight(int W, const vector<int> &wt, int n){
vector<vector<int> > M;
M.resize(n+1);
for(int i = 0; i < n+1; ++i){
M[i].resize(W+1);
}
for(int w = 0; w < W+1; w++){
M[0][w] = 0;
}
for(int i = 1; i < n+1; i++){
M[i][0] = 0;
}

for(int i = 1; i < n+1; i++){
for(int w = 0; w < W+1; w++){
if(wt[i] > w){
M[i][w] = M[i-1][w];
}

M[i][w] = max(M[i-1][w], wt[i] + M[i-1][W-wt[i]], W);
}
}for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= W; j++)
printf ("%4d", M[i][j]);
printf("\n");
}

return M[n][W];
}

int main()
{
//int val[] = {1, 1, 1};
int W;
int n;
cin >> W >> n;
vector<int> wt(n);
for(int i = 0; i < n; i++){
cin >> wt[i];
}
cout << optimal_weight(W, wt, n) << endl;

}

Спасибо за любую помощь!

0

algorithm c++c++14 dynamic subset-sum

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я понял! Вот мое решение:

#include <iostream>
#include <vector>
using namespace std;

using std::vector;

int optimal_weight(int W, const vector<int> &wt) {
//write your code here

int n = wt.size();
vector<vector<int> > matrix;
matrix.resize(W+1);
for(int i = 0; i < W+1; i++){
matrix[i].resize(n);
}
for(int j = 0; j < n; j++){
matrix[0][j] = 0;
}
for(int w = 0; w < W + 1; w++){
matrix[w][0] = 0;
}
for(int i = 1; i < n; i++){
for(int w = 1; w < W+1; w++){
matrix[w][i] = matrix[w][i-1];
if(wt[i] <= w){
//cout << wt[i] << endl;
int val = matrix[w-wt[i]][i-1] + wt[i];
if(matrix[w][i] < val){
matrix[w][i] = val;
}
}
}
}

return matrix[W][n-1];}

int main() {
int n, W;
std::cin >> W >> n;
vector<int> wt(n+1);
for (int i = 1; i < n+1; i++) {
wt[0]=0;
std::cin >> wt[i];
}
std::cout << optimal_weight(W, wt) << '\n';
}

1