#背包#动态规划#北京大学上机题

https://www.acwing.com/problem/content/3445/

思路：对背包dp模板稍加修改，注意转移方程和初始化的方法即可

解法：新建dp数组dp[i][j]，表示用i个物品凑齐j体积的方法总数，按顺序读取N和物品体积序列之后:

1.将dp数组的dp[0][0]置为0

2.用i和j进行遍历

a.对于每一个dp[i][j]，首先先把dp[i-1][j]（代表少一件凑齐j的方法）赋值给他，意味着这件物品不能使用，故保留上一种方法的数量

b.判断，如果此时可以使用这个物品，dp[i][j]就要再加上用i-1件物品凑齐j-arr[i]的方法

c.直到遍历结束，打印dp[n][40]即可

#include <bits/stdc++.h>

using namespace std;
int dp[50][50]; //dp[i][j]的值代表用i个物品凑齐j体积的方法数
int main(){
    int n;
    cin >> n;
    int arr[n+1];
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=40;j++){
            dp[i][j]=dp[i-1][j];
            if(j >= arr[i]){
                dp[i][j]+=dp[i-1][j-arr[i]];
            }
        }
    }
    printf("%d",dp[n][40]);
    return 0;
}