就是 01 背包，大意：給您 \(T\) 個空間大小的限制，有 \(M\) 個物品，第 \(i\) 件物品的重量為 \(c_i\) ，價值為 \(w_i\) ，要求挑選一些物品，使得總空間不超過 \(T\) ，且總價值最大，
考慮設 \(f_{i,j}\) 為 \(1\) ~ \(i\) 件物品，背包容量為 \(j\) 時的最大價值，那么假如不選第 \(i\) 件物品,則為 \(f_{i-1,j}\) 的子問題（背包內只有 \(i-1\) 個物品）；若選，則為 \(f_{i-1,j-w_i}+v_i\) 的子問題，
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int f[1001][1001],T,M,w[100001],v[100001];
int main()
{
cin>>T>>M;
for(int i=1;i<=M;i++)cin>>w[i]>>v[i];
for(int i=1;i<=M;i++)
for(int j=0;j<=T;j++)
if(j<w[i])f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
cout<<f[M][T]<<endl;
return 0;
}
注意到這種做法本題會被卡，可以優化成一維，但程序很難想，
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int f[1000001],T,M,w[1000001],v[1000001];
int main()
{
cin>>M>>T;
for(int i=1;i<=M;i++)cin>>w[i]>>v[i];
for(int i=1;i<=M;i++)
for(int j=T;j>=w[i];--j)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[T]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63273.html
標籤：C++
下一篇：【做題筆記】P1042 乒乓球