01背包问题

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

第 ii 件物品的体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤10000
0<vi,wi≤10000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

解题思路

1.暴力解法 二维动态规划

f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少

result=max{ f[ n ][ 0-v ] }

f[i][j]有以下两种取值

(1) 不选第i个物品，f[ i ][ j ] = f[ i-1 ][ j ];

(2) 选第i个物品，f[ i ][ j ] = f[ i-1 ][ j-v ];

//注意此时背包应该考虑为内存容量还有j-v时能放的最大价值量

最终f[ i ][ j ]在两种情况中取最大值:f[ i ][ j ] =max{ (1) , (2) }

初始化f[0]f[0]=0

直接上代码

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=1010;int n,m;
int f[N][N];
int v[N],w[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}}int res=0;for(int i=0;i<=m;i++) res=max(res,f[n][i]);cout<<res<<endl;
}

2.优化上述代码

用滚动数组来对空间进行优化

将状态f[i][j]优化到一维f[j]，只需要进行一个等价变形：

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）将状态f[j]定义：N 件物品的条件下，背包容量为 j 下的最优解。

（2）注意枚举背包容量 j 必须从 m 开始。

（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮 i - 1 的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，将会有 f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

这里其实可以简单的思考一下，我们是用小体积更新大体积，那么逆序的话就可以从使用前面还未更新的小体积（上一轮即i-1个物品）来进行更新后面的大体积（当前轮，即加入第i个物品），小体积的更新用不上大体积（所以，大体积提前更新到第i个也没有关系）

（4）例如，一维状态第i轮对体积为 33 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。

（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max( f[j], f[j - v[i]] + w[i] )。

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=1010;int n,m;//n为物品数,m为背包最大容积
int f[N];
int v[N],w[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}int res=f[m];cout<<res<<endl;
}

完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 ii 种物品的体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

 f[i] 表示总体积是i的情况下，最大价值是多少。
result = max{ f[0 ... m] }

for( int i = 0; i < n: ;i++)

        for(int j=v[i];j<=m;j++)

                f[j] = max( f[j],f[i]-v[u]]+w[i] );

数学归纳法：

1.假设考虑前i-1个物品之后，所有的f[j]都是正确的

2.证明，考虑玩第i个物品后，所有的f[j]也是正确的

对于某个j而言，如果最优解中包含k个v[i]；

f[ j - k* v[i] ];

则会从包含k-1个v[i]中去更新

f[ j - ( k-1) * v[ i ] -v[ i ] ]+ w[i] ]

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;int n,m;
int f[N];int main(){cin>>n>>m;for(int i=0;i<n;i++){int v,w;cin>>v>>w;for(int j=v;j<=m;j++)f[j]=max(f[j],f[j-v]+w);}cout<<f[m]<<endl;return 0;
}

多重背包问题

有 N 种物品和一个容量是 V 的背包。

第 ii 种物品最多有 sisi 件，每件体积是 vi，价值是 wi。

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

输入格式

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

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

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

数据范围

0<N,V≤100
0<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

暴力解法 

其实这道题只要参考01背包问题即可

f[i] 表示总体积为i的情况下,最大价值是多少

f[j] = max ( f[j], f[ j-v[i]]+w[i] ,f[ j - 2*v[i] ]+ 2 * w[i] , ... , f[ j-k*v[i] ] + k* w[i]);

第一种情况  初始化:f[i]=0;

则答案为f[m]

第二种情况  f[0]=0,f[i]=-INF , i != 0;

max{ f[ 0 ... m ]}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;int n,m;
int f[N];int main()
{cin>>n>>m;for(int i=0;i<n;i++){int v,w,s;cin>>v>>w>>s;for(int j=m;j>=0;j--){for(int k=1;k<=s&&k*v<=j;k++)f[j]=max(f[j],f[j - k * v] + k * w);}}cout<<f[m]<<endl;return 0;
}