佛山建站公司模板,移动健康app下载,凡科做的网站为什么打不开,wordpress搜索无效题目来源#xff1a;9. 分组背包问题 - AcWing题库 题目#xff1a;
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个#xff0c;同一组内的物品最多只能选一个。 每件物品的体积是 vij#xff0c;价值是 wij#xff0c;其中 i 是组号#xff0c;j 是组内编号。 … 题目来源9. 分组背包问题 - AcWing题库 题目
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个同一组内的物品最多只能选一个。 每件物品的体积是 vij价值是 wij其中 i 是组号j 是组内编号。
求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 NV 用空格隔开分别表示物品组数和背包容量。
接下来有 N 组数据
每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量每组数据接下来有 Si 行每行有两个整数 vij,wij用空格隔开分别表示第 i 个物品组的第 j 个物品的体积和价值
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤100 0Si≤100 0vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5输出样例
8
题目解析对于每组有s1种选择不选选第一个选第二个....选第s个
上代码
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N110;
int n,v;
int f[N],V[N],W[N];//f[i]代表i体积的最大价值 int main()
{cinnv;for(int i0;in;i){int s;cins;for(int j0;js;j)//遍历每个组 {cinV[j]W[j];}for(int jv;j0;j--)//遍历体积 for(int k0;ks;k)//遍历同一组的每个物品 {if(f[j]V[k])f[j]max(f[j],f[j-V[k]]W[k]);}}coutf[v];return 0;
}
