线性DP
背包问题
01背包
状态计算时 ，每个状态都有选或不选两种情况
f[i][j] = max(f[i][j],f[i -1][j - v[i]] + w[i]);
有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int v[N],w[N];
int main(void)
{
cin >> n >> m;
for(int i = 0;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][j],f[i-1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
完全背包
最朴素做法需要枚举k的次数（三维）
优化后变成二维
有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。
第 ii 种物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int v[N],w[N];
int main(void)
{
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 = 1;j<=m;j++)
{
f[i][j] = f[i-1][j];
if(j >= v[i])
f[i][j] = max(f[i][j],f[i][j -v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
多重背包问题
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值
直接枚举每次取得数量即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n,m;
int w[N],s[N],v[N];
int f[N][N];
int main(void)
{
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1;i <= n;i++)
for(int j = 0;j <=m;j++)
for(int k= 0;k <= s[i] && j >= v[i] * k;k++)
f[i][j] = max(f[i][j],f[i-1][j-v[i] * k] + w[i] * k);
cout << f[n][m] << endl;
return 0;
}
多重背包复杂版
0<N≤10000<N≤1000 0<V≤20000<V≤2000 0<vi,wi,si≤2000
利用二进制优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25000,M = 2010;
int n,m;
int v[N],w[N];
int f[M];
int main(void)
{
cin >> n >> m;
int cnt = 0;
for(int i = 1;i<=n;i++)
{
int k = 1;
int a,b,s;
cin >> a >> b >> s;
while(k<=s)
{
cnt++;
v[cnt] = a*k;
w[cnt] = b*k;
s = s - k;
k = k * 2;
}
/*
这里相当于是把 一个整数 s 划分成了二进制的数，然后利用二进制数的组合 可以把s个数分
成 logs 个数 然后利用这 logs 个数 可以组合成 0~s 之间的任意数 在这个题意中就可以把
取 0~s 个的所有情况包括了 这样就可以节省了许多时间
经过这个过程后 就会产生 相当于 01 背包的问题一样 许多只能取一次的数据
所以此时就可以利用 01 背包优化对此时的所有情况进行取 最大值 //
总而言之 本题 的主要思想就是 利用二进制优化 把 s 个情况分成 logs 个 在利用 01 背包
进行最后的结果的总运算
也可以理解为 cnt 这个数组已经报含了 在数组中取任意个数字的情况
*/
if( s > 0)
{
cnt ++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}
n = cnt;
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]);
cout << f[m] << endl;
return 0;
}
分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值
分组背包问题，枚举每一组的第几个物品被选
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N][N]; //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N]; //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j]; //读入
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j]; //不选
for(int k=0;k<s[i];k++){
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int w[N][N],v[N][N],s[N];
int f[N][N];
int n,m;
int main(void)
{
cin >> n >> m;
for(int i = 1; i <= n ; i ++)
{
cin >> s[i];
for(int j = 1 ; j <= s[i]; j++) cin >> v[i][j] >> w[i][j];
}
for(int i = 1; i <= n ; i++)
for(int j = 0; j <= m ; j ++)
{
f[i][j] = f[i - 1][j]; // 不选的情况
for(int k = 1 ; k <= s[i] ; k ++) // 枚举选的情况
{
if( j >= v[i][k])
f[i][j] = max(f[i][j] , f[i-1][j - v[i][k]] + w[i][k]);
}
}
cout << f[n][m] << endl;
return 0;
}