满背包问题，把体积和价值看成相等的。用滚动数组优化，然后额外开辟一个choice数组来记录每次的选择，然后回溯打印。因为要按字典序，先把价值进行排序。假如选最小的商品能装满m的话，那就把判断条件改成大于等于，然后最后来
#include<bits/stdc++.h> using namespace std; int dp[105]; int w[10005]; bool flag[10005]; bool choice[10005][105]; int n, m; bool cmp(int a, int b) {return a > b; } int main() {memset(flag, false, sizeof(flag));fill(choice[0], choice[0] +105, false);fill(dp, dp +105, 0);scanf("%d %d", &n, &m);int i, j;for (i = 1; i <= n; i++){scanf("%d", &w[i]);}sort(w+1, w + n+1,cmp);for (i = 1; i <= n; i++){for (j = m; j >= w[i]; j--){if (dp[j-w[i]]+w[i]>=dp[j]){dp[j] = dp[j - w[i]] + w[i];choice[i][j] = true;}}}int x=n, y=m;int num = 0;if (dp[m] != m){printf("No Solution\n");}else{while (x >= 1){if (choice[x][y] == true){flag[x] = true;//下标num++;y -= w[x];}x--;}for (i = n; i >= 1; i--){if (flag[i] == true){if (num - 1 > 0){printf("%d ", w[i]);num--;}elseprintf("%d\n", w[i]);}}} }
选择最小的那个。
