看到这个题，有了一个大胆的想法，对方案数进行背包，对于一个pos【钱数】就是把每种能买的菜的pos【钱数-菜价】加起来，POS存放的是方案数
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; int a[101]; for (int i = 0; i < n; i++){ cin >> a[i]; } int pos[1001] = { 1 }; for (int i = 0; i < n; i++){ for (int j = m; j >= a[i]; j--) { pos[j] += pos[j - a[i]]; } } cout << pos[m] << endl; return 0; }
原文：https://www.cnblogs.com/Vetsama/p/12288323.html