Причина неизвестного сигнала 6 - PullRequest
Новая
       74

Причина неизвестного сигнала 6

1 голос
/ 07 мая 2020

Вам дается набор золотых слитков, и ваша цель - унести в сумку как можно больше золота. Есть только одна копия каждого бара, и для каждого бара вы можете либо взять его, либо нет (следовательно, вы не можете взять долю бара). Описание проблемы Задача. Для n золотых слитков найдите максимальный вес золота, который помещается в мешок емкостью W. Формат ввода. Первая строка входных данных содержит вместимость ранца W и количество n слитков золота. Следующая строка содержит n целых чисел w0, w1, ..., wn − 1, определяющих веса слитков золота. Ограничения. 1 ≤ W ≤ 104; 1 ≤ n ≤ 300; 0 ≤ w0, ..., wn − 1 ≤ 105. Формат вывода. Выведите максимальный вес золота, который умещается в рюкзаке вместимостью W. Вот мой код. 

#include <bits/stdc++.h>
using namespace std;
int optimal(vector<int>&w,int W,int n){
vector<vector<int> > val(n+2,vector<int>(W+2));

  for(int j=0;j<=n;j++)
  {
for(int i=0;i<=W;i++)
  { if(i==0 || j==0){ val[j][i]=0;continue;}
    if(w[j]<=i)
    {
        val[j][i]=max(val[j-1][i],(w[j]+val[j-1][i-w[j]]));
        //cout<<val[j][i]<<endl;
    }
    else {val[j][i]=val[j-1][i];

  }}
  }
  int q1=val[n][W];
  return q1;
}
int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w;
  w.push_back(0);
  for (int i = 1; i <= n; i++) {
    std::cin >> w[i];
  }
 sort(w.begin(),w.end());
cout<<optimal(w,W,n);
}

Не могу придумать решение этой проблемы. Буду очень благодарен за любую помощь в этом вопросе. TIA.

...