按喜好程度排序, 每次按取的件数和当前花费金额分类记录, 剩下普通零食按完全背包更新就可以了, 这是后来改的, 不一定完全正确, 欢迎讨论..觉得不错的点个赞呗 #include<bits/stdc++.h> using namespace std; vector<int> f; bool cmp(const int& a, const int& b) { return f[a] < f[b]; } int main(){ int m, n, v, t; while (cin >> v >> n) { vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } cin >> m; f = vector<int>(n, n); for (int i = 0; i < m; i++) { cin >> t; f[t - 1] = i; } sort(a.begin(), a.end(), cmp); vector<vector<int> > dp(v / a[0] + 1, vector<int>(v + 1, 0)); int res = 0; // 先挑选最喜欢的零食, 无约束 for (int i = 0; i < v / a[0] + 1; i++) { dp[i][i * a[0]] = 1; } // 按喜欢程度依次挑选其他特别喜欢的零食, for(int i = 1; i < m; i++) { vector<vector<int>> t = move(dp); int size = v / a[i] + 1; dp = vector<vector<int> >(size, vector<int>(v + 1, 0)); for (int j = 1; j < t.size(); j++) { // 每次取的要比前一种要少 for (int k = min(size - 1, j - 1); k >= 0; k--) { for (int l = k * a[i]; l <= v; l++){ dp[k][l] = (dp[k][l] + t[j][l - k * a[i]]) % 10000007; } } } } // 统计各花费的方案数 vector<int> cur(v + 1, 0); for (int i = 0; i <= v; i++) { for (int j = 0; j < dp.size(); j++) { cur[i] = (cur[i] + dp[j][i]) % 10000007; } } // 按完全背包更新其余零食 for (int i = m; i < n; i++) { for (int j = a[i]; j <= v; j++) { cur[j] = (cur[j] + cur[j - a[i]]) % 10000007; } } cout << cur[v] << endl; } return 0; }