首页 > 其他分享 >AcWing 278. 数字组合

AcWing 278. 数字组合

时间:2023-04-02 11:47:54浏览次数:52  
标签:组合 int A1 A2 278 include dp AcWing

给定 N 个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数,表示 A1,A2,…,AN。

输出格式

包含一个整数,表示可选方案数。

数据范围

1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。

输入样例:

4 4
1 1 2 2

输出样例:

3

状态分析:

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+5;
int dp[N];
int main(){
    int n,m;
    cin>>n>>m;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        for(int j=m;j>=x;j--)dp[j]=max(dp[j],dp[j]+dp[j-x]);
    }
    cout<<dp[m]<<endl;
    return 0;
}

 

标签:组合,int,A1,A2,278,include,dp,AcWing
From: https://www.cnblogs.com/hxss/p/17280148.html

相关文章

  • AcWing 1022. 宠物小精灵之收服
    宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在......
  • AcWing 1024. 装箱问题
    有一个箱子容量为V,同时有n个物品,每个物品有一个体积(正整数)。要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。输入格式第一行是一个整数V,表示箱子容量。第二行是一个整数n,表示物品数。接下来n行,每行一个正整数(不超过10000),分别表示这n个物品的各自体积。......
  • AcWing 8. 二维费用的背包问题
    有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。输出最大价值。输入格式第一行三个整数,N,V,M,......
  • AcWing 9. 分组背包问题
    有N组物品和一个容量是V的背包。每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是vij,价值是wij,其中i是组号,j是组内编号。求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行有两个整数N,V,用空格隔开,分别......
  • AcWing 3. 完全背包问题
    有N种物品和一个容量是V的背包,每种物品都有无限件可用。第i种物品的体积是vi,价值是wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有N行,每行两个......
  • AcWing 4. 多重背包问题
    有N种物品和一个容量是V的背包。第i种物品最多有si件,每件体积是vi,价值是wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有N行,每行三个整数vi,wi,......
  • AcWing 2. 01背包问题
    有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是vi,价值是wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有N行,每行两个......
  • Acwing 799.最长连续不重复子序列
    原题链接代码#include<iostream>usingnamespacestd;constintN=100010;inta[N],f[N];intmain(){intn;cin>>n;intans=0,j=1;for(inti=1;i<=n;i++){scanf("%d",&a[i]);//读入该数组f[......
  • acwing 4405.统计子矩阵的和
    原题链接解题思路通过i和j来控制子矩阵的左右边界,通过s和t来控制子矩阵的上下边界,在子矩阵的和小于k时候,统计子矩阵的个数。代码#include<iostream>usingnamespacestd;constintN=550;inta[N][N];//i与j控制左右边界,st控制上下边界计算二维矩阵和intmai......
  • AcWing第97场周赛复盘总结
    4944.热身计算-AcWing题库给定两个正整数$a,b$,请你分别计算$\min(a,b)$以及$\lfloor\frac{|a-b|}{2}\rfloor$的值。$\lfloor\frac{|a-b|}{2}\rfloor$表示不大于$\frac{|a-b|}{2}$的最大整数。输入格式共一行,包含两个正整数$a,b$。输出格式共一......