原題
有?N�?組物品和一個容量是?V�?的背包。
每組物品有若干個，同一組內的物品最多只能選一個。
每件物品的體積是?vij���，價值是?wij���，其中?i�?是組號，j�?是組內編號。
求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大。
輸出最大價值。
輸入格式
第一行有兩個整數?N，V�，�，用空格隔開，分別表示物品組數和背包容量。
接下來有?N�?組數據：
- 每組數據第一行有一個整數?Si��，表示第?i�?個物品組的物品數量；
- 每組數據接下來有?Si��?行，每行有兩個整數?vij,wij���,���，用空格隔開，分別表示第?i�?個物品組的第?j�?個物品的體積和價值；
輸出格式
輸出一個整數，表示最大價值。
數據范圍
0<N,V≤1000<�,�≤100
0<Si≤1000<��≤100
0<vij,wij≤1000<���,���≤100
輸入樣例
3 5
2
1 2
2 4
1
3 4
1
4 5
輸出樣例：
8原題鏈接
傳送門?
代碼
#include<bits/stdc++.h>
using namespace std;const int N=110;int s[N];
int v[N][N],w[N][N];
int f[N];int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&s[i]);for(int j=0;j<s[i];j++){scanf("%d%d",&v[i][j],&w[i][j]);}}for(int i=0;i<n;i++){for(int j=m;j>=0;j--){for(int k=0;k<s[i];k++){if(v[i][k]<=j){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}printf("%d\n",f[m]);return 0;
}總結
1.首先是數據范圍比較小，只有100，可以使用N^3時間復雜度的算法通過這道題
2.給定的是n組物品，每一組物品里面有多件物品，一件物品只能選擇一次，本質上還是01背包，選或者不選，兩種情況，所以第二層循環還是從大往小枚舉背包容量
3.每一組里面只能選擇一件物品
4. 更多的理解之后有新的感想再補充
