济源城乡建设局网站,wordpress 淘宝联盟,做动效网站,动态域名可以做网站吗注意事项#xff1a; 本题是动态规划—01背包的扩展题#xff0c;优化思路不多赘述#xff0c;dp思路会稍有不同#xff0c;下面详细讲解。
题目#xff1a; 给定 N个正整数 A1,A2,…,AN#xff0c;从中选出若干个数#xff0c;使它们的和为 M#xff0c;…注意事项 本题是动态规划—01背包的扩展题优化思路不多赘述dp思路会稍有不同下面详细讲解。
题目 给定 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 cmath
#include cstring
#include iostream
#include algorithm
using namespace std;const int N 10010;
int n, m;
int v[N], f[N], s[N][N];//基础版二维
void base() {s[0][0] 1;for (int i 1; in; i) {for (int j 0; jm; j) {s[i][j] s[i-1][j];if (j v[i]) s[i][j] s[i-1][j-v[i]];}}cout s[n][m];
}//01背包优化一维滚动数组
void op() {f[0] 1;for (int i 1; in; i) {for (int j m; j0; j--) {f[j] f[j-v[i]];}}cout f[m];
}int main() {cin n m;for (int i 1; in; i) cin v[i];// base();op();return 0;
}思路 经典的y式dp法
1.状态表示 f[i][j]: 表示从前i个数中选总和刚好为j的方案属性为Count。
2.状态计算 以 选择/不选择 第i个物品为划分 1.当不选择第i个物品时: f[i][j] f[i-1][j] 2.当选择第二个物品时: f[i][j] f[i-1][j-v[i]]
切记我们这里f[i][j]中记录的是前i个数中总和为j的方案总数 是在计算数量也就是。
还有就是初始步骤f[0][0]为1 因为从前0个数中选总和为0也是一种方案。
声明 算法思路来源为y总详细请见https://www.acwing.com/ 本文仅用作学习记录和交流
