题目：https://www.nowcoder.com/practice/9aaea0b82623466a8b29a9f1a00b5d35?tpId=40&tqId=21390&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

代码

  1. #include <cstdio>
  2. #include <iostream>
  3. using namespace std;
  4. const int obj_num = 25;
  5. const int max_val = 9999999;
  6. int dp[obj_num][max_val]; // dp的含义是背包容量为i的时候，有几种选择方法凑出j
  7. int a[25];
  8. int main(){
  9.     int n;
  10.     while(scanf("%d", &n) != EOF){
  11.         for(int i = 1; i <= n; i++) {
  12.             scanf("%d", &a[i]);
  13.             dp[i][0] = 1;
  14.         }
  15.         dp[0][0] = 1;
  16.         for(int i = 1; i <= n; i++){
  17.             for(int j = 1; j <= 40; j++){
  18.                 dp[i][j] = dp[i - 1][j];
  19.                 if(j >= a[i])
  20.                     dp[i][j] += dp[i - 1][j - a[i]];
  21.             }
  22.         }
  23.         printf("%d\n", dp[n][40]);
  24.     }
  25. }