题目2. 01背包问题题目描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行两个整数NV用空格隔开分别表示物品数量和背包容积。接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0 N, V ≤ 10000 vi, wi≤ 1000时空限制1s / 64MB输入样例4 5 1 2 2 4 3 4 4 5输出样例8思路分析状态f [ i ] [ j ] f[i][j]f[i][j]表示所有从前i ii个物品中选且总体积≤ j ≤j≤j的最大价值。状态计算就是集合划分一般考虑最后一步划分在本道题中最后一步就是第i ii个物品的选法因此按照不选第i ii个物品和选第i ii个物品将集合划分不选i ii相当于从前i − 1 i-1i−1个物品中选且总体积≤ j ≤j≤j的最大价值即f [ i − 1 ] [ j ] f[i-1][j]f[i−1][j]选i ii比较难表示。可以考虑将所有选法中的第i ii个物品都去掉这样做不影响最大价值的然后再加上第i ii个物品。这样相当于从前i − 1 i-1i−1个物品中选且总体积≤ j − v [ i ] ≤j-v[i]≤j−v[i]的最大价值然后再加上第i ii个物品的价值即f [ i − 1 ] [ j − v [ i ] ] w [ i ] f[i-1][j-v[i]]w[i]f[i−1][j−v[i]]w[i]那么每个选法相当于从这两个子集中选最大的即m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] w [ i ] ) max(f[i-1][j],f[i-1][j-v[i]]w[i])max(f[i−1][j],f[i−1][j−v[i]]w[i])注意不选i ii是任何选法都可以的而选i ii要基于当前背包体积j ≥ v [ i ] j≥v[i]j≥v[i]的前提初始化f[0][0 ~ V]表示从前 0 个物品中选且总体积 ≤ 0 ~ V 的最大价值也就是没有选任何物品那么最大价值应该为0。结果最终要求的是从前n nn个物品中选且总体积≤ V ≤V≤V的最大价值即f [ n ] [ V ] f[n][V]f[n][V]代码1二维数组#includebits/stdc.husingnamespacestd;constintN100010;intn,V,v[N],w[N],f[N][N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i];for(inti1;in;i)for(intj0;jV;j){//如果i1时,f[i][0]需要被更新f[i][j]f[i-1][j];if(jv[i])f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}coutf[n][V];return0;}优化f [ i ] [ j ] f[i][j]f[i][j]只依赖第i − 1 i-1i−1层的状态可以删去第一维直接用f [ j ] f[j]f[j]表示第i ii层的状态f [ i ] [ j ] f [ i − 1 ] [ j ] ; f[i][j]f[i-1][j];f[i][j]f[i−1][j];删去第一维就变成f [ j ] f [ j ] ; f[j]f[j];f[j]f[j];就是一个恒等式可以删去当j jj在0 ~ v[i]-1时是不执行i f ( j v [ i ] ) f [ i ] [ j ] m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] w [ i ] ) ; if(jv[i]) f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);if(jv[i])f[i][j]max(f[i][j],f[i−1][j−v[i]]w[i]);的因此可以直接将j jj的初始值设置为v [ i ] v[i]v[i]这样可以删去i f ( j v [ i ] ) if(jv[i])if(jv[i])对于f [ i ] [ j ] m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] w [ i ] ) ; f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);f[i][j]max(f[i][j],f[i−1][j−v[i]]w[i]);如果直接删去第一维会变成f [ j ] m a x ( f [ j ] , f [ j − v [ i ] ] w [ i ] ) ; f[j]max(f[j],f[j-v[i]]w[i]);f[j]max(f[j],f[j−v[i]]w[i]);这和删之前的二维状态不等价因为此时这个语句相当于f [ i ] [ j ] m a x ( f [ i ] [ j ] , f [ i ] [ j − v [ i ] ] w [ i ] ) ; f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);f[i][j]max(f[i][j],f[i][j−v[i]]w[i]);但f [ i ] [ j ] f[i][j]f[i][j]应该是基于i − 1 i-1i−1层的状态的。那么为了让f [ i ] [ j ] f[i][j]f[i][j]仍依赖于上一层就要让f [ j − v [ i ] ] f[j-v[i]]f[j−v[i]]先别更新即在计算第i ii层时让f [ j − v [ i ] ] f[j-v[i]]f[j−v[i]]在f [ j ] f[j]f[j]之后再更新那么怎么解决呢可以让j jj逆序遍历即f o r ( i n t j V ; j v [ i ] ; j − − ) for(int jV;jv[i];j--)for(intjV;jv[i];j−−)由于j jj是严格 j − v [ i ] j-v[i]j−v[i]的因此计算第i ii层时会先更新f [ j ] f[j]f[j]的值代码2一维数组#includebits/stdc.husingnamespacestd;constintN100010;intn,V,v[N],w[N],f[N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i];for(inti1;in;i)for(intjV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[V];return0;}结果