hihoCoder #1364 : 奖券兑换（超大0-1背包问题）
发布时间
阅读量：
阅读量
题目所对应的网络地址为：https://hihocoder.com/problemset/problem/1364>
#1364 : 奖券兑换
时间限制设定为20000毫秒
单个测试点的时间上限为1000毫秒
内存使用上限为256兆字节
描述
小Hi在游乐园中收集到了M张奖券，这些奖券可用于换取各类奖品。
目前可选择的奖品共有N种。其中，第i种奖品的兑换所需奖券数量为Wi，对应的价值为Pi。
在奖券总数不超过M的前提下，小Hi能够获取到的奖品总价值最高可达多少？
输入
第一行给出两个整数N与M的值。
随后的N行中，每行包含两个整数Wi与Pi。
针对50%的数据规模：N和M的取值范围为1到1000。
针对100%的数据规模：N和M的取值范围为1到105，同时Pi与Wi的取值范围均为1到10。
小标题
每一行输入一个整数，用以体现所能达到的最大价值。
样例输出
解析：针对01背包问题，若直接按照10^10的规模进行处理，显然会导致时间复杂度过高而无法在合理时间内完成计算。考虑到实际情况下所有可能的状态数仅为10*10，因此可以将原本的01背包问题转化为多重背包问题进行求解。
代码：
#include<bits/stdc++.h>
#define 全部评论 (0)
还没有任何评论哟~