1 01背包输出方案2 按字典序顺序输出所选背包物品举个例子输入的数据↓N5,V51:v2w32:v1w03:v1w04:v2w35:v1w5按照逆向dp构造出的dp数组dp[i][j]表示体积为j时放第i件物品的最大价值。如下表所示dp[1][V]存储了n件物品体积为V时的最大价值。搜索时正序遍历dp数组内层循环逆序遍历体积如果dp[i1][curV - v[i]] w[i] dp[i][curV]),说明第i件物品有选。体积/物品012345物品10558811物品2055888物品3055888物品4055888物品5055555参考代码#includebits/stdc.husingnamespacestd;intn,V;intv[1005],w[1005];intdp[1005][1005];// dp[i][j]: 从 i 到 n容量 j 的最大价值boolchosen[1005];intmain(){cinnV;for(inti1;in;i){cinv[i]w[i];}// 逆序 DPfor(intin;i1;i--){for(intj0;jV;j){dp[i][j]dp[i1][j];if(jv[i]){dp[i][j]max(dp[i][j],dp[i1][j-v[i]]w[i]);}}}// 从前往后贪心保证字典序最小intcurVV;for(inti1;in;i){if(curVv[i]dp[i1][curV-v[i]]w[i]dp[i][curV]){chosen[i]true;curV-v[i];}}for(inti1;in;i){if(chosen[i]){couti ;}}cout\n;return0;}例题2 洛谷P2066对于编号小的尽量少分配机器再做dp时考虑正向。搜索方案的时候逆向搜索。参考代码#includebits/stdc.husingnamespacestd;#defineintlonglongintn,m,a[20][20],dp[20][20];intansk[20];signedmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cina[i][j];for(inti1;in;i){for(intjm;j1;j--){dp[i][j]dp[i-1][j];for(intk1;kj;k)dp[i][j]max(dp[i][j],dp[i-1][j-k]a[i][k]);}}coutdp[n][m]endl;intcurMm;for(intin;i1;i--){for(intkcurM;k1;k--){if(dp[i][curM]dp[i-1][curM-k]a[i][k]){ansk[i]k;curM-k;break;}}}for(inti1;in;i)couti ansk[i]endl;return0;}