c++寶物篩選問題怎么解決

這篇文章主要介紹“c++寶物篩選問題怎么解決”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“c++寶物篩選問題怎么解決”文章能幫助大家解決問題。

題目描述

小 FF 找到了王室的寶物室，里面堆滿了無數價值連城的寶物。

這下小 FF 可發財了，嘎嘎。但是這里的寶物實在是太多了，小 FF 的采集車似乎裝不下那么多寶物。看來小 FF 只能含淚舍棄其中的一部分寶物了。

小 FF 對洞穴里的寶物進行了整理，他發現每樣寶物都有一件或者多件。他粗略估算了下每樣寶物的價值，之后開始了寶物篩選工作：小 FF 有一個最大載重為 W 的采集車，洞穴里總共有 n 種寶物，每種寶物的價值為 v_i ，重量為 w_i，每種寶物有 m_i件。小 FF 希望在采集車不超載的前提下，選擇一些寶物裝進采集車，使得它們的價值和最大。

輸入格式 第一行為一個整數 n 和 W，分別表示寶物種數和采集車的最大載重。

接下來 nn 行每行三個整數 v_i,w_i,m_i

輸出格式 輸出僅一個整數，表示在采集車不超載的情況下收集的寶物的最大價值。

輸入輸出樣例 輸入 #1復制 4 20 3 9 3 5 9 1 9 4 2 8 1 3 輸出 #1復制 47 說明/提示 對于 30\%30% 的數據，n≤∑m ≤10 ^4，0≤W≤10 ^3 對于 100\%100% 的數據，n≤∑m ≤10 ^5 ，0≤W≤4×10 ^4，1≤n≤100。

思路說明

這道題的難點在于規定了每個寶物的數量，如果直接上三層循環又會tle所以做法稍微有些改變

代碼實現

30分做法（TLE）

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int u[10006],v[11006],m[10006];
int n,t;
int f[100006];
int main(){
  cin>>n>>t;
  for(int i=1;i<=n;i++){
    cin>>u[i]>>v[i]>>m[i];
  }

  for(int i=1;i<=n;i++){
    for(int k=1;k<=m[i];k++){
      for(int j=t;j>=1;j--){
        if(j>=v[i]){
          f[j]=max(f[j],f[j-v[i]]+u[i]);
        }
      }
    }
  }
  cout<<f[t];
}

AC做法

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a,b,c;
int u[10006],v[10006],m[10006];
int n,t;
int f[100006];
int main(){
  cin>>n>>t;
  int cnt;
  cnt=0;
  for(int i=1;i<=n;i++){
    cin>>a>>b>>c;
  for(int j=1;j<=c;j<<=1){
    u[++cnt]=j*a,v[cnt]=j*b,c-=j;//可以將寶物按照2，4，8...的順序結合起來，如果最后有剩余再單獨判斷一下
    //因為寶物按照順序組合起來，所以時間和價值也要處理，這樣做的好處是可以節省大量時間
  
  }
  if(c){//如果有剩余的情況特殊處理一下
    u[++cnt]=c*a;
    v[cnt]=c*b;
  }
  }
  for(int i=1;i<=cnt;i++){
      for(int j=t;j>=1;j--){
        if(j>=v[i]){
          f[j]=max(f[j],f[j-v[i]]+u[i]);
        }
    }
  }
  cout<<f[t];
}

關于“c++寶物篩選問題怎么解決”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。