多重部分和问题

模板题

代码

#include<iostream>
using namespace std;
#define Max_K 100000
int dp[Max_N+1][Max_K+1];
int a[Max_N];
int m[Max_N];
int n,K;
 
void solve()
{
    dp[0][0]=0;
    for(int j=1;j<=K;j++)
      dp[0][j]=-1;          //用前0种数凑成和不为0的，肯定不行
  
  //dp[i][j] 用前i种数(下标0~i-1)在能凑成和为j时，第i个数(下标为i-1)
  //最多可以剩余多少个，-1表示前i种数凑不成和为j 
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=K;j++)
        {
            if(dp[i-1][j]>=0)     
            //如果前i-1种数就能凑成和为j,那么第i个数a[i-1]可以一个都不用，全部剩下来
                dp[i][j]=m[i-1];
            else             //前i-1种数凑不成和为j,那么就用第i个数a[i-1]尝试凑
            {
    //如果要凑的和j小于a[i-1],那么肯定凑不成j   ------   j<a[i-1]
    //无法用前i个数凑不成和j-a[i-1],那么无论再加不加上一个数a[i-1],都凑不成和j  -----dp[i][j-a[i-1]<0
    //如果在用前i个数能凑成和j-a[i-1],但是这时候a[i-1]数用完了，那么也是凑不成的 ------dp[i][j-a[i-1]=0
                if(j<a[i-1] || dp[i][j-a[i-1]]<=0)
                 dp[i][j]=-1;
                else
    //在前i种数能凑成和j-a[i-1]并且数a[i-1]还有剩余，那么是能凑成的,再用掉一个a[i-1]，所以个数减一 
                 dp[i][j]=dp[i][j-a[i-1]]-1; 
            } 
            //cout<<"dp["<<i<<"]["<<j<<"]:"<<dp[i][j]<<endl;   //测试使用 
        }
    } 
      //dp[n][K]>=0表明前n个数(a[0]~a[n-1])在凑成和为K时,数a[i-1]不剩余或者还有剩余，
    //但是不管剩余还是不剩余，都是能凑成和为j 
    if(dp[n][K]>=0) cout<<"Yes\n";
    else cout<<"No\n";

    return ;
}

int main()
{
    cin>>n>>K;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    for(int i=0;i<n;i++)
    {
        cin>>m[i];
    }
    solve();
}

Holding Bin-Laden Captive!

这道题的数组得开的很小心，太小了会wa 太大了会MLE
定义dp[i][j]为前i种组成j的时候第i中数剩余多少

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int dp[5][15000];
int a[4]={0,1,2,5};
int m[5];
int n,K=15000;

int main()
{
    while(cin>>m[1]>>m[2]>>m[3]&&(m[1]!=0||m[2]!=0||m[3]!=0)){
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=3;i++)
            for(int j=0;j<=K;j++){
                if(dp[i-1][j]>=0)
                    dp[i][j]=m[i];
                else if(a[i]>j||dp[i][j-a[i]]<=0){
                    dp[i][j]=-1;
                }else{
                    dp[i][j]=dp[i][j-a[i]]-1;
                }
            }
        int res;
        for(int j=0;j<=K;j++){
            if(dp[3][j]==-1)
            {
                res=j;
                break;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}