首页 > 代码库 > POJ1742可行性背包

POJ1742可行性背包

2024-07-03 18:17:19   225人阅读


题目：

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
题目意思就是：

一定量的硬币，问可以凑出多少不同的价值。

之所以做这题，是因为在LTC的男人八题看到的。

之前其实真的没做过可行性背包，当时第一反应就是拍了一个优化的多重背包，结果果然是TLE了。之后看题解，原来有O（nm）的姿势，补上。

最近改用vim了!codeblocks,byebye!

周日就是GDCPC了，虽然队伍的缺陷非常多，但是，尽力吧！

/*************************************************************************
    > OS     : Linux 3.2.0-60-generic #91-Ubuntu
    > Author : yaolong
    > Mail   : dengyaolong@yeah.net
    > Created Time: 2014年05月09日 星期五 10:23:35
 ************************************************************************/

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 105
#define MAXV 100005
int cnt[MAXN],val[MAXN];
int used[MAXV];
bool f[MAXV];
int n,V;
int coins;
/*可行性背包，当问题仅仅是问能否装到，那么只要达到过就不要再做了*/
void AMultipack(int val,int num){
    memset(used,0,sizeof(used));
    for(int j=val;j<=V;j++){
        if(!f[j]&&f[j-val]&&used[j-val]<num){
            //要求f[j]没有存在过，但是f[j-val]是之前达到的，且还可以购买
            f[j]=true;
            used[j]=used[j-val]+1;
            coins++;
        }
    }
}
int main(){
    int n;
    int i,j,k;
    while(scanf("%d%d",&n,&V)&&(n||V)){
    
        for(i=0;i<n;i++){
            scanf("%d",val+i);
        }
        for(i=0;i<n;i++){
            scanf("%d",cnt+i);
        }
        coins=0;
        memset(f,0,sizeof(f));
        f[0]=true;
        for(i=0;i<n;i++){
            AMultipack(val[i],cnt[i]);
        }
        printf("%d\n",coins);
    }
    return 0;
}




联系
我们