1

你得到一套金条，你的目标是尽可能多地把金条装进你的包里。每个条形图只有一个副本，对于每个条形图，您可以选择或不接受（因此您不能选择一个条形图的一小部分）。问题描述任务。给定 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。

4

0 回答 0