大英县住房和城乡建设局网站,学做网站论坛全部视频,网站验证,保山市网站建设原题
有 N#xfffd; 组物品和一个容量是 V#xfffd; 的背包。
每组物品有若干个#xff0c;同一组内的物品最多只能选一个。 每件物品的体积是 vij#xfffd;#xfffd;#xfffd;#xff0c;价值是 wij#xfffd;#xfffd;#xfffd;#xff0c;其中 …原题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个同一组内的物品最多只能选一个。 每件物品的体积是 vij价值是 wij其中 i 是组号j 是组内编号。
求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 NV用空格隔开分别表示物品组数和背包容量。
接下来有 N 组数据
每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量每组数据接下来有 Si 行每行有两个整数 vij,wij,用空格隔开分别表示第 i 个物品组的第 j 个物品的体积和价值
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000,≤100 0Si≤1000≤100 0vij,wij≤1000,≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5输出样例
8
原题链接
传送门
代码
#includebits/stdc.h
using namespace std;const int N110;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 i0;in;i){scanf(%d,s[i]);for(int j0;js[i];j){scanf(%d%d,v[i][j],w[i][j]);}}for(int i0;in;i){for(int jm;j0;j--){for(int k0;ks[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. 更多的理解之后有新的感想再补充
