动态规划(背包问题):POJ 1742 Coins

时间:2022-10-02 22:33:38
Coins
Time Limit: 3000MS   Memory Limit: 30000K
Total Submissions: 32955   Accepted: 11199

Description

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and
C1,C2,C3...Cn corresponding to the number of Tony's coins of value
A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay
use these coins.

Input

The
input contains several test cases. The first line of each test case
contains two integers n(1<=n<=100),m(m<=100000).The second line
contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn
(1<=Ai<=100000,1<=Ci<=1000). The last test case is followed
by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4   
 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int num[],v[];
int dp[][];
int main()
{
int n,m,now,pre;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
for(int i=;i<=n;i++)scanf("%d",&v[i]);
for(int i=;i<=n;i++)scanf("%d",&num[i]);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
now=i%;pre=(i-)%;
dp[now][]=;
for(int j=;j<=m;j++){
if(dp[pre][j]<=num[i-])dp[now][j]=;
if(j>=v[i]&&dp[now][j-v[i]]+<=num[i])
dp[now][j]=min(dp[now][j],dp[now][j-v[i]]+);
}
} int ans=;
for(int i=;i<=m;i++)
if(dp[now][i]<=num[n])
ans++; printf("%d\n",ans);
}
return ;
}

动态规划(背包问题):POJ 1742 Coins的更多相关文章

  1. hdu 2844 poj 1742 Coins

    hdu 2844 poj 1742 Coins 题目相同,但是时限不同,原本上面的多重背包我初始化为0,f[0] = 1;用位或进行优化,f[i]=1表示可以兑成i,0表示不能. 在poj上运行时间正 ...

  2. 题解报告:hdu 2844 &amp&semi; poj 1742 Coins(多重部分和问题)

    Problem Description Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. On ...

  3. &lbrack;POJ 1742&rsqb; Coins 【DP】

    题目链接:POJ - 1742 题目大意 现有 n 种不同的硬币,每种的面值为 Vi ,数量为 Ni ,问使用这些硬币共能凑出 [1,m] 范围内的多少种面值. 题目分析 使用一种 O(nm) 的 D ...

  4. poj 1742 Coins (动态规划,背包问题)

    Coins Time Limit: 3000MS   Memory Limit: 30000K Total Submissions: 32977   Accepted: 11208 Descripti ...

  5. poj 1742 Coins(dp之多重背包&plus;多次优化)

    Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar. ...

  6. POJ 1742 Coins&lpar;多重背包&comma; 单调队列&rpar;

    Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar. ...

  7. Poj 1742 Coins(多重背包)

    一.Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dolla ...

  8. poj 1742 Coins (多重背包)

    http://poj.org/problem?id=1742 n个硬币,面值分别是A1...An,对应的数量分别是C1....Cn.用这些硬币组合起来能得到多少种面值不超过m的方案. 多重背包,不过这 ...

  9. POJ 1742 Coins &lpar;多重背包&rpar;

    Coins Time Limit: 3000MS   Memory Limit: 30000K Total Submissions: 28448   Accepted: 9645 Descriptio ...

随机推荐

  1. -&lbrack;NSNull countByEnumeratingWithState&colon;objects&colon;count&colon;&rsqb;&colon;

    当数组为空时遍历数组容易出这样的问题, -[NSNull countByEnumeratingWithState:objects:count:]: unrecognized selector sent ...

  2. NetworkComms框架介绍 完美支持TCP&sol;UDP协议

    NetworkComms网络通信框架序言 英文文章地址 :http://www.networkcomms.net/tcp-udp-connections/ NetworkComs.Net无缝的支持TC ...

  3. easy ui 表单提交添加遮罩,避免数据重复提交

    如下图: //点击提交按钮保存数据 $('#btn_submit').click(function () { //增加遮罩层 $.messager.progress({ title: '温馨提示', ...

  4. Webapp meta标签解决移动缩放的问题

    webapp开发初期,会碰到在pc端开发好的页面在移动端显示过大的问题,这里需要在html head中加入meta标签来控制缩放 <meta name=" viewport" ...

  5. PHP Database ODBC 之 ODBC

    ODBC 是一种应用程序编程接口(Application Programming Interface,API),使我们有能力连接到某个数据源(比如一个 MS Access 数据库). 创建 ODBC ...

  6. 【QT相关】QT&plus;opencv环境配置

    在qt msvc2010版软件中使用opencv2.4.9进行库函数配置.仅适用于windows下. INCLUDEPATH += $$PWD/../../../opencv/build/includ ...

  7. Delphi判断一个字符是否为汉字的最佳方法

    //判断字符是否是汉字 function IsHZ(ch: WideChar): boolean; var i:integer; begin i:=ord(ch); if( i<19968) o ...

  8. python实战第一天-paramiko模块并练习

    操作系统 Ubuntu 15.10 IDE & editor JetBrains PyCharm 5.0.2 ipython3 Python版本 python-3.4.3 安装paramiko ...

  9. Vue&period;js02:数据绑定v-model用法

    <!-- v-model 实现数据的双向绑定 --> <!-- v-model 只能用在表单元素中 --> 示例: <!DOCTYPE html> <!-- ...

  10. js如何复制一个对象?

    方法一: 把原来对象的属性遍历一遍,赋给一个新的对象. //深复制对象方法 var cloneObj = function (obj) { var newObj = {}; if (obj insta ...