题目12. 背包问题求具体方案题目描述有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。第 i 件物品的体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出 字典序最小的方案。这里的字典序是指所选物品的编号所构成的序列。物品的编号范围是1 … N 1…N1…N。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品数量和背包容积。接下来有N NN行每行两个整数v i v_ivi,w i w_iwi用空格隔开分别表示第i ii件物品的体积和价值。输出格式输出一行包含若干个用空格隔开的整数表示最优解中所选物品的编号序列且该编号序列的字典序最小。物品编号范围是1 … N 1…N1…N。数据范围0 N , V ≤ 1000 0N,V≤10000N,V≤10000 v i , w i ≤ 1000 0v_i,w_i≤10000vi,wi≤1000时空限制1s / 64MB输入样例4 5 1 2 2 4 3 4 4 6输出样例1 4代码1用一个二维数组记录每次的选择#includebits/stdc.husingnamespacestd;constintN100010;intn,V,v[N],w[N],f[N][N];boolg[N][N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i];for(intin;i1;i--)for(intj0;jV;j){f[i][j]f[i1][j];if(v[i]j){inttmpf[i1][j-v[i]]w[i];if(tmpf[i][j]){//因为字典序最小,所以尽可能选择i小的,这里取到等于f[i][j]tmp;g[i][j]true;}}}for(inti1,jV;in;i)if(g[i][j]){couti ;j-v[i];}return0;}代码#includeiostreamusingnamespacestd;constintMaxN100010,MaxV100010;intN,V,v[MaxN],w[MaxN],f[MaxN][MaxV];intmain(){cinNV;for(inti1;iN;i){cinv[i]w[i];}for(intiN;i1;i--){for(intj0;jV;j){f[i][j]f[i1][j];if(v[i]j){f[i][j]max(f[i][j],f[i1][j-v[i]]w[i]);}}}// f[1][V]是最大价值intjV;for(inti1;iN;i){if(v[i]jf[i][j]f[i1][j-v[i]]w[i]){couti ;j-v[i];}}return0;}结果
题目12. 背包问题求具体方案题目描述有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。第 i 件物品的体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出 字典序最小的方案。这里的字典序是指所选物品的编号所构成的序列。物品的编号范围是1 … N 1…N1…N。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品数量和背包容积。接下来有N NN行每行两个整数v i v_ivi,w i w_iwi用空格隔开分别表示第i ii件物品的体积和价值。输出格式输出一行包含若干个用空格隔开的整数表示最优解中所选物品的编号序列且该编号序列的字典序最小。物品编号范围是1 … N 1…N1…N。数据范围0 N , V ≤ 1000 0N,V≤10000N,V≤10000 v i , w i ≤ 1000 0v_i,w_i≤10000vi,wi≤1000时空限制1s / 64MB输入样例4 5 1 2 2 4 3 4 4 6输出样例1 4代码1用一个二维数组记录每次的选择#includebits/stdc.husingnamespacestd;constintN100010;intn,V,v[N],w[N],f[N][N];boolg[N][N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i];for(intin;i1;i--)for(intj0;jV;j){f[i][j]f[i1][j];if(v[i]j){inttmpf[i1][j-v[i]]w[i];if(tmpf[i][j]){//因为字典序最小,所以尽可能选择i小的,这里取到等于f[i][j]tmp;g[i][j]true;}}}for(inti1,jV;in;i)if(g[i][j]){couti ;j-v[i];}return0;}代码#includeiostreamusingnamespacestd;constintMaxN100010,MaxV100010;intN,V,v[MaxN],w[MaxN],f[MaxN][MaxV];intmain(){cinNV;for(inti1;iN;i){cinv[i]w[i];}for(intiN;i1;i--){for(intj0;jV;j){f[i][j]f[i1][j];if(v[i]j){f[i][j]max(f[i][j],f[i1][j-v[i]]w[i]);}}}// f[1][V]是最大价值intjV;for(inti1;iN;i){if(v[i]jf[i][j]f[i1][j-v[i]]w[i]){couti ;j-v[i];}}return0;}结果
