简单的背包问题

解题思路:简单的背包问题

注意事项:

参考代码:

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

    int n,m,i,j,a[40],dp[20005];

    cin>>n;

    for(i=0;i<=n;i++)

         dp[i]=n;

    cin>>m;

    for(i=0;i<m;i++)

        cin>>a[i];

    for(i=0;i<m;i++)

        for(j=n;j>=a[i]&&dp[j-a[i]]>=a[i];j--)

            dp[j]=min(dp[j-a[i]]-a[i],dp[j]);

    cout<<*min_element(dp,dp+n+1);

    return 0;

}