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

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

題目描述

小 FF 找到了王室的寶物室，里面堆滿了無數(shù)價(jià)值連城的寶物。

這下小 FF 可發(fā)財(cái)了，嘎嘎。但是這里的寶物實(shí)在是太多了，小 FF 的采集車似乎裝不下那么多寶物?？磥硇?FF 只能含淚舍棄其中的一部分寶物了。

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

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

接下來 nn 行每行三個(gè)整數(shù) v_i,w_i,m_i

輸出格式 輸出僅一個(gè)整數(shù)，表示在采集車不超載的情況下收集的寶物的最大價(jià)值。

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

思路說明

這道題的難點(diǎn)在于規(guī)定了每個(gè)寶物的數(shù)量，如果直接上三層循環(huán)又會(huì)tle所以做法稍微有些改變

代碼實(shí)現(xiàn)

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...的順序結(jié)合起來，如果最后有剩余再單獨(dú)判斷一下
    //因?yàn)閷毼锇凑枕樞蚪M合起來，所以時(shí)間和價(jià)值也要處理，這樣做的好處是可以節(jié)省大量時(shí)間
  
  }
  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];
}

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