shunfurh
编程介的小学生
2019-01-05 00:40
采纳率: 92.7%
浏览 734

整数的拆分和求和,如何使用动规来实现,动归解决数组问题,C语言

Problem Description
You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs p dollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.

For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.

Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.

1≤T≤20000
0≤p≤109
0≤ci≤100000

Output
For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output '-1'.

Sample Input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0

Sample Output
9
-1
36

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • caozhy
    已采纳
    点赞 评论
  • lmz4201
    dnz01 2019-01-06 10:53

    多重背包问题,机试指南上有

    直接用0-1背包比较麻烦,但也可行。

    ci>p的币种不用
    每个币种组合成它的1,2,4,8直到k-2^c+1,总和为k。每个币种的值和数量算起来,列成数组。

    动态规划
    p=0返回0,
    否则dp[p+1],开始dp[0]=0,其他-1。flag=1;
    如果dp[p-ci]!=-1,就可以马上输出其+1值,置flag=0;
    否则逆向扫描行,dp[i]=max{dp[i-币值](不是-1)+1,dp[i]}
    结束后flag=0,则输出dp[p]=-1

    当然一直扫完再输出也可以。

    而不做分组也可以,毕竟p才109.

    点赞 评论

相关推荐