多重部分和问题

傷城~ 2022-07-24 11:21 135阅读 0赞

## 问题及代码：    ##

有n种不同大小的数字a\[i\]，每种各m\[i\]个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。

代码① dp\[i\]表示以a\[i\]为末尾的最长上升子序列的长度。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 10010
    
    int n,K,a[MAXN],m[MAXN];
    bool dp[MAXN][MAXN];
    
    void solve()
    {
        dp[0][0]=true;
        int i,j,k;
        for(i=0; i<n; ++i)
            for(j=0; j<=K; ++j)
                for(k=0; k<=m[i]&&k*a[i]<=j; ++k)
                    dp[i+1][j]|=dp[i][j-k*a[i]];
        if(dp[n][K]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    int main()
    {
        int i;
        cin>>n;
        for(i=0; i<n; ++i)
            cin>>a[i];
        for(i=0; i<n; ++i)
            cin>>m[i];
        cin>>K;
        solve();
        return 0;
    }
    /*
    n a m k
    3
    3 5 8
    3 2 2
    17
    */

代码② dp\[i\]表示长度为i+1的上升子序列中末尾元素的最小值。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 10010
    
    int n,K,a[MAXN],m[MAXN];
    int dp[MAXN];
    
    void solve()
    {
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        int i,j;
        for(i=0; i<n; ++i)
            for(j=0; j<=K; ++j)
            {
                if(dp[j]>=0) dp[j]=m[i];
                else if(j<a[i]||dp[j-a[i]]<=0) dp[j]=-1;
                else dp[j]=dp[j-a[i]]-1;
            }
        if(dp[K]>=0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    int main()
    {
        int i;
        cin>>n;
        for(i=0; i<n; ++i)
            cin>>a[i];
        for(i=0; i<n; ++i)
            cin>>m[i];
        cin>>K;
        solve();
        return 0;
    }
    /*
    n a m k
    3
    3 5 8
    3 2 2
    17
    */