poj 1742 Coins 多重双肩包变形

poj 1742 Coins 多重背包变形

题目：http://poj.org/problem?id=1742

用bool dp[i]来表示价格i是否能被表示出。

直接做：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX_N=100001;
bool dp[MAX_N];
int num[105],val[105];
int main()
{
	int N,M;
	while(cin>>N>>M)
	{
		if(N+M==0)break;
		for(int i=0;i<N;i++) cin>>val[i];
	 	for(int i=0;i<N;i++) cin>>num[i];
	 	
	 	//memset(dp,0,sizeof(dp));
	 	for(int i=0;i<=M;i++) dp[i]=0;
	 	
	 	dp[0]=1;
	 	for(int i=0;i<N;i++){
	 		for(int j=M;j>=1;j--){
		 		for(int k=0;k<=num[i]&&k*val[i]<=j;k++){
	 				dp[j] |= dp[j-k*val[i]];
		 		}
		 	}
	 	}
	 	int ans=0;
	 	for(int i=1;i<=M;i++) if(dp[i]) ans++;
	 	cout<<ans<<endl;
	}
}

这个会超时，优化一下，膜拜楼教主：

#include <cstdio>
#include <iostream>
using namespace std;
const int max_s = 107;
bool f[100007];
int w[max_s],b[max_s];
//f[i]来表示当前i价格是否出现过，
int sum[100007];//当价格达到i时，最多使用这一种硬币的次数
int main()
{
    int n,V,i,j;
    while(scanf("%d%d",&n,&V),n+V)
    {
        int ans=0;
        for(i=0;i<n;i++)
        	scanf("%d",&w[i]);
        for(i=0;i<n;i++)
        	scanf("%d",&b[i]);
        for(i=f[0]=1;i<=V;i++) f[i]=0;
        
        for(i=0;i<n;i++)
        {
            for(j=0;j<=V;j++) sum[j]=0;//关键是用sum来限定了次数
            for(j=w[i];j<=V;j++)//从w[i]到V循环检查看是否能够出现前边没有出现的价格
            {
                if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i])
                //如果j价格没有出现过，且j-w[i]出现过，并且使用i硬币的次数没有超出给定的数量
                {
                    f[j]=1;//标记为已出现过
                    sum[j]=sum[j-w[i]]+1;//使用次数+1
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
}