Coins

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

8
4

#include<iostream>
#include<cstring>
using namespace std;
int dp[100050],c[100050];

int main(){
    int n,m;
    while(cin>>n>>m && (n||m)){
        int i,j;
        int u[105],v[105];
        for(i=0;i<=m;i++)  dp[i]=0;
        for(i=1;i<=n;i++)   cin>>u[i];
        for(i=1;i<=n;i++)   cin>>v[i];

        /*int r=1;
        for(i=1;i<=n;i++){
            for(j=1;j<=v[i];j<<=1){
                c[r++]=j*u[i];
                v[i]-=j;
            }
            if(v[i]>0)  c[r++]=v[i]*u[i];
        }
        for(i=1;i<r;i++)
            for(j=m;j>=[i];j--)
                dp[j]=max(dp[j],dp[j-c[i]]+c[i]);*/
        for(i=1;i<=n;i++){
            for(int k=0;k<=m;k++)   c[k]=0;
            for(j=u[i];j<=m;j++)
            if(dp[j]<dp[j-u[i]]+u[i] && c[j-u[i]]<v[i]){
                dp[j]=dp[j-u[i]]+u[i];
                c[j]=c[j-u[i]]+1;
            }
        }

        int ans=0;
        for(i=1;i<=m;i++)
            if(dp[i]==i)  ans++;
        cout<<ans<<endl;

    }
    return 0;
}

hdu 2844 Coins DP

原文：http://blog.csdn.net/hyccfy/article/details/42874525