企业官网建设流程全解析

题目：2. 01背包问题

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 1000
0 < v_i, w_i≤ 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（二维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10;intn,V,v[N],w[N],f[N][N];intmain(){cin>>n>>V;for(inti=1;i<=n;i++)cin>>v[i]>>w[i];for(inti=1;i<=n;i++)for(intj=0;j<=V;j++){//如果i>1时,f[i][0]需要被更新f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}cout<<f[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(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);if(j>=v[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(j>=v[i])if(j>=v[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 j=V;j>=v[i];j--)for(intj=V;j>=v[i];j−−)，由于j jj是严格＞ j − v [ i ] ＞j-v[i]＞j−v[i]的，因此计算第i ii层时，会先更新f [ j ] f[j]f[j]的值

代码2（一维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10;intn,V,v[N],w[N],f[N];intmain(){cin>>n>>V;for(inti=1;i<=n;i++)cin>>v[i]>>w[i];for(inti=1;i<=n;i++)for(intj=V;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[V];return0;}

结果