题目11. 背包问题求方案数题目描述有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。第i ii件物品的体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出 最优选法的方案数。注意答案可能很大请输出答案模10 9 7 10^971097的结果。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品数量和背包容积。接下来有N NN行每行两个整数v i v_ivi,w i w_iwi用空格隔开分别表示第i ii件物品的体积和价值。输出格式输出一个整数表示 方案数 模10 9 7 10^971097的结果。数据范围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输出样例2代码1二维数组#includeiostreamusingnamespacestd;constintMaxN100010,MaxV100010,mod1e97;intN,V,v[MaxN],w[MaxN],f[MaxN][MaxV],g[MaxN][MaxV];intmain(){cinNV;for(inti1;iN;i){cinv[i]w[i];for(intj0;jV;j){f[i][j]f[i-1][j];if(v[i]j){f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}}}g[0][0]1;for(inti1;iN;i){for(intj0;jV;j){if(f[i][j]f[i-1][j]){g[i][j](g[i][j]g[i-1][j])%mod;}if(jv[i]f[i][j]f[i-1][j-v[i]]w[i]){g[i][j](g[i][j]g[i-1][j-v[i]])%mod;}}}intres0;for(intj0;jV;j){if(f[N][j]f[N][V]){res(resg[N][j])%mod;}}coutres;return0;}代码2一维数组#includeiostream#includecstringusingnamespacestd;constintMaxV100010,mod1e97;intN,V,f[MaxV],g[MaxV];intmain(){cinNV;g[0]1;for(inti1;iN;i){intv,w;cinvw;for(intjV;jv;j--){intmaxwmax(f[j],f[j-v]w);intans0;if(maxwf[j]){ansg[j];}if(maxwf[j-v]w){ansg[j-v];}g[j]ans%mod;f[j]maxw;}}intmaxw0;for(intj0;jV;j){maxwmax(maxw,f[j]);}intres0;for(intj0;jV;j){if(maxwf[j]){res(resg[j])%mod;}}coutres;return0;}代码3一维数组#includebits/stdc.husingnamespacestd;constintN100010,MOD1e97;intn,V,v[N],w[N],f[N],g[N],ans;intmain(){cinnV;for(inti1;in;i)cinv[i]w[i];memset(f,-0x3f,sizeoff);f[0]0;g[0]1;for(inti1;in;i)for(intjV;jv[i];j--){intmaxxmax(f[j],f[j-v[i]]w[i]);intcnt0;if(maxxf[j])cntg[j];if(maxxf[j-v[i]]w[i])cntg[j-v[i]];f[j]maxx;g[j]cnt%MOD;ansmax(ans,f[j]);}intcnt0;for(intjV;j0;j--)if(f[j]ans)cnt(cntg[j])%MOD;coutcnt;return0;}结果