http://poj.org/problem?id=3260

这个题目有点小难,我开始没什么头绪,感觉很乱。

后来看了题解,感觉豁然开朗。

题目大意:就是这个人去买东西,东西的价格是T,这个人拥有的纸币和数量。让你求这个人买东西的纸币量加上老板找给他的纸币量最少是多少。

这个老板用于这个人拥有的纸币种类,数量是无限。

思路:

思路就是这个人看成多重背包,老板看成完全背包,f1[i] 表示这个人花了 i 的钱用的最少的纸币。f2[i] 表示老板凑出 i 的钱用的最少的纸币。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e5 + ;
int N, V;
int weight[maxn], num[maxn];
int f1[maxn], f2[maxn], V1;
void zeroonepack(int weight, int val, int f[]) {
for (int i = V; i >= weight; i--) {
f[i] = min(f[i], f[i - weight] + val);
}
} void completepack(int weight, int val, int f[]) {
for (int i = weight; i <= V; i++) {
f[i] = min(f[i], f[i - weight] + val);
}
} void multiplepack(int weight, int val, int count, int f[]) {
if (count*weight >= V) completepack(weight, val, f);
else {
int t = ;
while (t < count) {
zeroonepack(weight*t, val*t, f);
count -= t;
t *= ;
}
zeroonepack(count*weight, count*val, f);
}
} int main() {
while (scanf("%d%d", &N, &V1) != EOF) {
int max_val = ;
for (int i = ; i <= N; i++) {
scanf("%d", &weight[i]);
max_val = max(max_val, weight[i]);
}
for (int i = ; i <= N; i++) scanf("%d", &num[i]);
V = max_val * max_val + V1 + ;
memset(f1, inf, sizeof(f1));
memset(f2, inf, sizeof(f2));
f1[] = , f2[] = ;
for (int i = ; i <= N; i++) {
multiplepack(weight[i], , num[i], f1);//顾客
}
for (int i = ; i <= N; i++) {
completepack(weight[i], , f2);
}
//printf("v=%d v1=%d\n", V, V1);
int ans = inf;
for (int i = ; i <= V - V1; i++) {
if (f1[V1 + i] != inf && f2[i] != inf) {
ans = min(f1[V1 + i] + f2[i], ans);
}
}
if (ans != inf) printf("%d\n", ans);
else printf("-1\n");
}
return ;
}

最新文章

  1. easycwmp的编译
  2. numberOfRowsInSection方法什么时候调用
  3. 对象的比较与排序:IComparable和IComparer接口
  4. class文件概述
  5. [转]C++11 多线程
  6. arcgis desktop按ctrl键后地图乱移的解决办法
  7. 如何自适应网页的协议(http/https/……)
  8. Hadoop入门实践之从WordCount程序说起
  9. Google protobuf安装
  10. Spring中Bean实例的生命周期及其行为
  11. 用Jquery 仿VS 样式的 导航栏插件
  12. 动态规划(斜率优化):BZOJ 3675 [Apio2014]序列分割
  13. Linux常用的系统监控shell脚本
  14. Quartz.NET学习系列
  15. AngularJS -- Bootstrap(启动器)
  16. css盒子居中定位问题
  17. Xamarin Essentials教程获取路径文件系统FileSystem
  18. odp.net连接方式,部署问题总结
  19. Python中操作HTTP请求的urllib模块详解
  20. multi-threads JavaEE 容器

热门文章

  1. 数论-质因数(gcd) UVa 10791 - Minimum Sum LCM
  2. 腾讯云集群服务部署mysql并挂载到服务器
  3. JACTF Web部分
  4. python 进阶篇 函数装饰器和类装饰器
  5. Scrapy模拟登录信息
  6. 《Metasploit魔鬼训练营》第一章实践作业
  7. 2019-2020-1 20199325《Linux内核原理与分析》第六周作业
  8. 快速部署一个Kubernetes集群
  9. Linux中的常用符号
  10. JavaScript Array every()&some()&reduce()方法