計蒜客第四章：蒜頭君的積木

計蒜客習題：蒜頭君的積木

題目

樣例

代碼

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int W,n,s[20],w[20],mi=1000,www,sss,dp[1<<16+5];
    cin>>W>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i]>>w[i];
    memset(dp,999999,sizeof(dp));
    for(int i=0;i<1<<n;i++)
    {
        www=0;
        sss=0;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j ))
            {
                www+=w[j+1];
                sss=max(sss,s[j+1]);
            }
        }
        if(www<=W) dp[i]=sss;
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=i;j;j=(j-1)&i)
            dp[i]=min(dp[i],dp[j]+dp[j^i]);
    cout<<dp[(1<<n)-1];
    return 0;
}