神奇的背包-遞歸+動态規劃-百練

輸入

輸入的第一行是正整數n (1 <= n <= 20)，表示不同的物品的

數目。接下來的n行，每行有一個1到40之間的正整數，分别

給出a 1 ，a 2 ……a n 的值。

輸出

輸出不同的選擇物品的方式的數目。

輸入樣例

3

20

 輸出樣例

62

枚舉每個物品是選還是不選，共2 20 種情況

​

枚舉的解法

#include<stdio.h>
int a[100];
int n;
int total[100]={0};
int f(int m,int k)
{
 
    if(m==0)
    {
    return 1;
    }
    if(k>=n)
    {
    return 0;
    }
    return  total[k]=f(m,k+1)+f(m-a[k],k+1);
}
int main()
{
 
scanf("%d",&n);
for(int i=0;i<n;i++)
{
  scanf("%d",&a[i]);
}
printf("%d",f(40,0));
for(int i=0;i<n;i++)
{
    printf("%d",total[i]);
}
return 0;
}