CH5201 数组组合【01背包】-白红宇的个人博客

CH5201 数组组合【01背包】

发布日期：2021-10-22 10:56:35 浏览次数：10 分类：技术文章

本文共 1039 字，大约阅读时间需要 3 分钟。

5201 数字组合 0x50「动态规划」例题

描述

在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)，再读入N个正数（可以有相同的数字，每个数字均在1000以内），在这N个数中找出若干个数，使它们的和是M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。

输入格式

第一行是两个数字，表示N和M。

第二行起是N个数。

输出格式

就一个数字，表示和为M的组合的个数。

样例输入

4 41 1 2 2

样例输出

思路：

非常基础的01背包问题 dp[i][j]为前i个数选出和为j的若干个数的方案数

实际上i的这一维是不需要的，因为i+1都是在i的基础上做的

采用倒序循环，循环到j时，后半部分j~m处于第i阶段，前半部分处于第i-1阶段

1 #include 
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 9 #define inf 0x3f3f3f3f10 using namespace std;11 typedef long long LL;12 13 int n, m;14 const int maxn = 105;15 int v[maxn], dp[10005];16 17 int main()18 {19 scanf("%d%d", &n, &m);20 for(int i = 0; i < n; i++){21 scanf("%d", &v[i]);22 }23 24 memset(dp, 0, sizeof(dp));25 dp[0] = 1;26 for(int i = 0; i < n; i++){27 for(int j = m; j >= v[i]; j--){28 dp[j] += dp[j - v[i]];29 }30 }31 printf("%d\n", dp[m]);32 return 0;33 }

转载于:https://www.cnblogs.com/wyboooo/p/9750264.html

转载地址：https://blog.csdn.net/weixin_30326745/article/details/95614008 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：中英文对照 —— 政治

下一篇：用列表实现一个简单的图书管理系统 python

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！