多重部分和 poj1742
2024-08-24 15:47:45
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.
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
多重部分和问题:
有n中大小不同的数字,每种c[i]个,判断这些数字之中能否选出若干个使其和为K
此题是让求K<=m时,有多少个解 一个一般性的代码如下
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int n, m;
int a[];
int c[];
int dp[][]; int main(int argc, char const *argv[])
{
//freopen("input.txt","r",stdin);
while(scanf("%d %d",&n,&m) != EOF && (n != && m != )) {
for(int i = ; i < n; i++) {
scanf("%d",&a[i]);
}
for(int i = ; i < n; i++) {
scanf("%d",&c[i]);
}
memset(dp, , sizeof(dp));
dp[][] = ;
for(int i = ; i < n; i++) {
for(int j = ; j <= m; j++) {
for(int k = ; k <= c[i] && k * a[i] <= j;k++) {
dp[i+][j] = dp[i+][j]| dp[i][j-k*a[i]];
}
}
}
int ans = ;
for(int i = ; i <= m; i++) {
if(dp[n][i] > ) {
ans++;
}
}
printf("%d\n",ans);
}
return ;
}
若用dp[i+1][j]表示用前i个数相加和为j时第i种数最多能剩余几个(不能得到和为-1)
可得代码如下
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int n, m;
int a[];
int c[];
int dp[]; int main(int argc, char const *argv[])
{
//freopen("input.txt","r",stdin);
while(scanf("%d %d",&n,&m) != EOF && (n != && m != )) {
for(int i = ; i < n; i++) {
scanf("%d",&a[i]);
}
for(int i = ; i < n; i++) {
scanf("%d",&c[i]);
}
memset(dp, -, sizeof(dp));
dp[] = ;
for(int i = ; i < n; i++) {
for(int j = ; j <= m; j++) {
if(dp[j] >= ) {
dp[j] = c[i];
}
else if(j < a[i] || dp[j - a[i]] <= ) {
dp[j] = -;
}
else {
dp[j] = dp[j - a[i]] - ;
}
}
}
int ans = ;
for(int i = ; i <= m; i++) {
if(dp[i] >= ) {
ans++;
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- ***PHP 数组排序 +php二维数组排序方法(PHP比较器)
- Android 代理服务器为全网提供代理
- xcode6.4 7.2下载地址
- bzoj 2806: [Ctsc2012]Cheat 后缀自动机DP
- 今天才知道mysql
- 基于visual Studio2013解决面试题之0609寻找链表公共节点
- SWFUpload简单使用样例 Java版(JSP)
- Android布局解析,图文(转)
- Spring Ioc介绍和Bean的实例化
- 【转载】史上最全:TensorFlow 好玩的技术、应用和你不知道的黑科技
- Python定期删除文件、整理文件夹
- citySelect省市区jQuery联动插件
- linux服务不支持chkconfig的解决
- 【读书笔记】Linux内核设计与实现(第五章)
- OSAL工作机制分析
- Recursion递归
- IOS子视图超过父视图frame后,无法交互响应
- git fatal: The remote end hung up unexpectedly 错误
- Laravel trait 使用心得
- PHP扩展功能----发送邮件