题目概述:
分组背包
时间限制:1000ms
内存限制:128MB
一个旅行者有一个最多能装 V 公斤的背包,现在有 n 件物品,它们的重量分别是 W1,W2 ,...,Wn,它们的价值分别为 C1,C2,...,Cn 这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
输入格式
第一行:三个整数,V(背包容量,1≤V≤200),N(物品数量,1≤N≤30)和 T (最大组号,1≤T≤10);
第 2..N+1 行:每行三个整数 Wi,Ci,Pi(1≤Wi≤V,1≤Ci≤1000,1≤Pi≤T),表示每个物品的重量,价值,所属组号。
整体思路:
需要对每组物品做一个01背包
1、快速的遍历每一组的物品
需要将物品按组号分类 -- 二维 vector
2、需要遍历每个物品的两个属性
需要用结构体vector
3、AC代码:
注意:for(int k=0;k<v[i].size();k++)不要写成for(int k=0;k<=v[i].size()-1;k++)不然会RE,这个点差点给我卡死了
适用于数据偏大的一维dp代码: