CJOJ 2040 【一本通】分组背包(动态规划)

时间:2022-08-26 13:15:59

CJOJ 2040 【一本通】分组背包(动态规划)

Description

一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

Input

输入有多组数据,每组数据的第一行:三个整数,V(背包容量,V<=200),N(物品数量,N<=30)和T(最大组号,T<=10);

第2..N+1行:每行三个整数Wi,Ci,P,表示每个物品的重量,价值,所属组号。

Output

对于每组数据输出仅一行,一个数,表示最大总价值。

Sample Input

10 6 3

2 1 1

3 3 1

4 8 2

6 9 2

2 8 3

3 9 3

Sample Output

20

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2040

Source

动态规划

解决思路

原来的背包问题是第i件物品选与不选,而到了分组背包,只需要改成在一个组里面选第几个或是不选这和组。我们令F[i][j]表示前i组选j重量的物品,所以有动态转移方程:

F[i][j]=max(F[i-1][j],F[i-1][j-V[i][k]]+W[i][k]) (k表示选择第i组里的第k件)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std; const int maxN=40;
const int maxV=300;
const int maxT=15;
const int inf=2147483647; class Item
{
public:
int weight,value;
}; int n,V,T;
vector<Item> C[maxT];
int F[maxT][maxV]={0}; int main()
{
int a,b,c;
cin>>V>>n>>T;
for (int i=1;i<=n;i++)
{
cin>>a>>b>>c;
C[c].push_back((Item){a,b});
}
int Ans=0;
for (int i=1;i<=T;i++)
{
//for (int j=0;j<C[i].size();j++)
//for (int k=0;k<=V;k++)
for (int k=0;k<=V;k++)
{
for (int j=0;j<C[i].size();j++)
{
if (k-C[i][j].weight>=0)
F[i][k]=max(F[i][k],max(F[i-1][k],F[i-1][k-C[i][j].weight]+C[i][j].value));
else
F[i][k]=max(F[i][k],F[i-1][k]);
Ans=max(Ans,F[i][k]);
}
//cout<<F[i][k]<<' ';
}
//cout<<endl;
}
cout<<Ans<<endl;
return 0;
}

CJOJ 2040 【一本通】分组背包(动态规划)的更多相关文章

  1. Codeforces 946 D&period;Timetable-数据处理&plus;动态规划&lpar;分组背包&rpar; 处理炸裂

    花了两个晚上来搞这道题. 第一个晚上想思路和写代码,第二个晚上调试. 然而还是菜,一直调不对,我的队友是Debug小能手呀(真的是无敌,哈哈,两个人一会就改好了) D. Timetable   tim ...

  2. B - ACboy needs your help(动态规划,分组背包)

    B - ACboy needs your help Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & ...

  3. BZOJ1296 &lbrack;SCOI2009&rsqb;粉刷匠 动态规划 分组背包

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1296 题意概括 有 N 条木板需要被粉刷. 每条木板被分为 M 个格子. 每个格子要被刷成红色或蓝 ...

  4. 洛谷 P1273 有线电视网 && caioj 1109 树形动态规划(TreeDP)4:比赛转播(树上分组背包总结)

    从这篇博客往前到二叉苹果树都可以用分组背包做 这依赖性的问题,都可以用于这道题类似的方法来做 表示以i为根的树中取j个节点所能得的最大价值 那么每一个子树可以看成一个组,每个组里面取一个节点,两个节点 ...

  5. 洛谷P1757 通天之分组背包 &lbrack;2017年4月计划 动态规划06&rsqb;

    P1757 通天之分组背包 题目背景 直达通天路·小A历险记第二篇 题目描述 自01背包问世之后,小A对此深感兴趣.一天,小A去远游,却发现他的背包不同于01背包,他的物品大致可分为k组,每组中的物品 ...

  6. 树形DP&plus;(分组背包&vert;&vert;二叉树&comma;一般树&comma;森林之间的转换)codevs 1378 选课

    codevs 1378 选课 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond  题目描述 Description 学校实行学分制.每门的必修课都有固定的学分 ...

  7. 基于粒子群算法的分组背包MATLAB实现

    抽空看了一段时间的粒子群算法,这里仅针对其应用于动态规划中的背包问题的情况做下总结归纳,其他应用可以之后想到了再添加. 一:分组背包问题简介 假设有3个组,每组有2个物品,每种物品有3种属性,价值.体 ...

  8. HDU 1712 ACboy needs your help(分组背包)

    题意:给你n的课程组,每个课程组有m个课程,每个课程有一个完成时间与价值.问在m天内每组课程组最多选择一个,这样可以得到的最大价值是多少 题解:分组背包,其实就是每个课程组进行01背包,再在课程组内部 ...

  9. Codeforces Round &num;383 &lpar;Div&period; 2&rpar; D 分组背包

    给出一群女孩的重量和颜值 和她们的朋友关系 现在有一个舞台 ab是朋友 bc是朋友 ac就是朋友 给出最大承重 可以邀请这些女孩来玩 对于每一个朋友团体 全邀请or邀请一个or不邀请 问能邀请的女孩的 ...

随机推荐

  1. Linux进程间通信之消息队列

    本文依据以下思路展开,首先从宏观上阐述消息队列的机制,然后以具体代码为例进一步阐述该机制,最后试着畅想一下该通信机制潜在的应用. 消息队列是在两个不相关进程间传递数据的一种简单.高效方式,她独立于发送 ...

  2. 两台笔记本搭建openvswitch网络

    环境说明: 笔记本A.B均运行Ubuntu 14.04,两台笔记本通过无线网卡上网,用一根网线连接两台笔记本的有线网卡. 网络拓扑: 其中,vm1 vm2 S1位于笔记本A,vm3 vm4 S2位于笔 ...

  3. STM32f103------按键处理

    (1)按键去抖 /******************************************函数名称:Key_Scan(GPIO_TypeDef*GPIOx,u16 GPIO_pin)*描 ...

  4. rails console --sandbox出现的安装错误解决方案

    rails中可以用使用console命令行来测试运行rails应用程序,但是采用源码编译安装的话可能缺少readline动态库,导致ruby无法使用这个库此时如果调用rails console(rai ...

  5. Android Map新用法:MapFragment应用

    MapView ,MapActivity 这种的局限在于,必须要继承MapActivity,否则无法使用MapView,但是,MapFragment 这种的局限在于,必须要安装Google Play ...

  6. 【Beta】 第七次Daily Scrum Meeting

    第七次meeting会议 [Beta] 第七次Daily Scrum Meeting 一.本次会议为第七次meeting会议 二.时间:10:00AM-10:20AM 地点:禹州楼 三.会议站立式照片 ...

  7. Android中的intent属性

    android之Intent的七大属性 2015年04月03日 ⁄ Android ⁄ 共 14866字 ⁄ 字号 小 中 大 ⁄ 1条评论 Intent用于封装程序的“调用意图”.两个Activit ...

  8. iOS Swift基础知识代码

    推荐:Swift学习使用知识代码软件 //集合类型 数组 字典 func array1(){ var arr = [","dd"] //简单写法 var arr1 = [ ...

  9. Selenium WebDriver的工作原理

    先通过一个简单的类比说个好理解的,这个比喻是我从美版知乎Quora上看到的,觉得比较形象.好理解拿来用用. 我们可以把WebDriver驱动浏览器类比成出租车司机开出租车. 在开出租车时有三个角色: ...

  10. GUI学习之五——QAbstractButton类学习笔记

    今天总结一下AbstractButton类的学习笔记. 一.描述 AbstractButton是对各种按键的抽象类他的继承关系是这样的 首先,QAbstractButton继承了QWidget类的各种 ...