【板+背包】多重背包 HDU Coins
2024-10-20 11:44:28
http://acm.hdu.edu.cn/showproblem.php?pid=2844
【题意】
- 给定n种价值为Ci,个数为Wi的硬币,问在1~V中的这些数中哪些数能由这些硬币组成?
【思路】
- 多重背包,二进制优化,时间复杂度为O(V*log∑ni)
【Accepted】
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector> using namespace std;
typedef long long ll;
const int maxn=1e5+; int n,v;
int c[maxn],w[maxn];
int dp[maxn];
void ZOP(int cost,int wei)
{
for(int i=v;i>=cost;i--)
{
dp[i]=max(dp[i],dp[i-cost]+wei);
}
} void CPP(int cost,int wei)
{
for(int i=cost;i<=v;i++)
{
dp[i]=max(dp[i],dp[i-cost]+wei);
}
} void MTP(int cost,int wei,int cnt)
{
if(v<=cnt*cost)
{
CPP(cost,wei);
return;
}
int k=;
while(k<=cnt)
{
ZOP(k*cost,k*wei);
cnt-=k;
k*=;
}
ZOP(cnt*cost,cnt*wei);
}
int main()
{
while(~scanf("%d%d",&n,&v))
{
if(n==&&v==) break;
for(int i=;i<n;i++)
{
scanf("%d",&c[i]);
}
for(int i=;i<n;i++)
{
scanf("%d",&w[i]);
}
memset(dp,,sizeof(dp));
for(int i=;i<n;i++)
{
MTP(c[i],c[i],w[i]);
}
int cnt=;
for(int i=;i<=v;i++)
{
if(dp[i]==i)
{
cnt++;
}
}
printf("%d\n",cnt);
}
return ;
}
背包模板
最新文章
- 修改phpcms会员登录后头部登陆条的会员名称不带括号
- 移动应用开发测试工具Bugtags集成和使用教程
- web前端开发教程系列-2 - 前端开发书籍分享
- 使用Sqlserver Management Studio 导入导出 Excel的方法
- 01. 把存储过程结果集SELECT INTO到临时表
- js 配置基础启动文件
- Qt_chartdirector图形开发
- 最长回文字符串(manacher算法)
- c++子类和父类成员函数重名
- 基于visual Studio2013解决C语言竞赛题之1022最大数最小数
- mysql B+树 Cardinality MRR
- HAUT--1262--魔法宝石(暴力)
- 20150605面试汇总--js与java的差别
- 类和对象的创建过程(元类,__new__,__init__,__call__)
- SpringBoot2.0之六 多环境配置
- 探索JavaScript中Null和Undefined的深渊
- 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165225
- 最小表示法模板(洛谷P1368 工艺)(最小表示法)
- Python模块学习 - fabric
- 018_mac写权限的问题