今天開始寫背包問題，基本按照背包九講的內容，打算真整個寫一遍（如果不打算放棄的話）,還望點個關注，
01背包：給n個物品，每個物品只能選一次，背包最大可容納V的物品
這里使用二維的樸素寫法，時間復雜度為o（N*V）;
題目：洛谷1048
ac代碼如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[110][1010];//狀態 i是第i個物品 j是容積為j 的情況
int v[110],w[110];
int main()
{
int T,M;
cin>>T>>M;
for(int i=1;i<=M;i++) cin>>v[i]>>w[i];
for(int i=1;i<=M;i++)
{
for(int j=1;j<=T;j++)
{
if(j<v[i]) f[i][j]=f[i-1][j];//如果容積不夠裝下，直接復制上一件物品的容積相同的情況
else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//如果可以裝下，f[i-1][j]是不裝,f[i-1][j-v[i]]+w[i]是不可以裝下的情況
}
}
cout<<f[M][T];
return 0;
}
類似的題目：洛谷 1802
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/465996.html
標籤：其他