dp专题 神奇的口袋

有一个口袋容积为m，有n个物品，题目的体积为a1,a2,a3…an。把m装满有多少种不同的装法。

递归：
int dfs(int n, int m)/*从n个物品中选出总体积为m的选法*/
{
    if(m==0)
        return 1;
    if(n<=0)
        return 0;

    return dfs(n-1, m)+(m>=a[n]?dfs(n-1, m-a[n]):0);/*可以记忆化递归*/
}

递推：
dp[i][j]=dp[i-1][j]+(j>=a[i]?dp[i-1][j-a[i]]:0);

初始条件：dp[i][0]=1; （0<=i<=n）/*全部不选*/

递归：（可以转化成记忆化递归）
#include<bits/stdc++.h>
using namespace std;

int a[100];
int dp[100][100]={0};

int main()
{
    int n, m;
    cin>>n>>m;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j]+(j>=a[i]?dp[i-1][j-a[i]]:0);
        }
    }
    cout<<dp[n][m]<<endl;

    return 0;
}

递推：
#include<bits/stdc++.h>
using namespace std;

int a[100];

int dfs(int n, int m)
{
    if(m==0)
        return 1;
    if(n<=0)
        return 0;

    return dfs(n-1, m)+(m>=a[n]?dfs(n-1, m-a[n]):0);
}

int main()
{
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cout<<dfs(n, m)<<endl;

    return 0;
}