有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。输出背包可容纳的最大价值。
（1）二维做法（从前 i 个物品中选，并且体积不超过 j 的最大价值）时间复杂度o（nm）
公式：f [i] [j] = max( f [i-1] [ j ] , f [i-1] [j - v[i]] + w[i])
两种情况选最大值：1.不选第i件物品（ f [i-1] [ j ]）
2.选第 i 件物品（f [i-1] [j - v[i]] + w[i]）
代码
#include
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N][N];
int main()
{
int n,m;
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])//j-v[i] 必须 >= 0
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout< （2）一维做法（从前 i 个物品中选，并且体积不超过 j 的最大价值）
公式：f [j] = max( f [ j ] , f [j - v[i]] + w[i])
和上述二维做法类似：1.不选第i件物品（ f [ j ]）
2.选第 i 件物品（f [j - v[i]] + w[i]）
代码
#include
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N];
int main()
{
int n,m;
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]);
}
}
cout< 解释一下为什么是逆序
如果从小到大枚举，f[j]就会被更新（加入f[10]=max(f[10],f [ 10- 6 ] + w[10]) （v[10]=6), 发现f [ 4 ] 在前面（）已经被更新过了，而不是上一层i-1时的f [4 ] 值了)
如果从大到小枚举，f[10]就会先被更新，此时用到的f[<=10]的值还没被更新（可以认为是i-1层的值）
附一个大佬的详细解释
AcWing 2. 01背包问题 - AcWing
2.完全背包问题有 N 件物品和一个容量是 V 的背包。每件物品可以无限使用。第 i 件物品的体积是 vi，价值是 wi。输出背包可容纳的最大价值。
与01不同的是完全背包可以无限使用
（1）二维做法（从前 i 个物品中选，并且体积不超过 j 的最大价值）时间复杂度o（nm）
公式：f [i] [j] = max( f [i-1] [ j ] , f [i] [j - v[i]] + w[i])
两种情况选最大值：1.不选第i件物品（ f [i-1] [ j ]）
2.选第 i 件物品（f [i] [j - v[i]] + w[i]）
公式推导过程：
1.不选那第i个物品（f[i-1][j])
2.选第i个物品，且第二个物品选k个（k=1，2，3，4，..... , 直到背包装不下)
此时 f[i][j] = max ( f[i-1][j] , max (f[i-1][ j - 1*v]+ 1* w , f[i-1][ j - 2*v] +2* w , f[i-1][ j - 3*v] + 3* w , ..... + f[i-1][ j - k*v] + k* w))
f[i][j-v] = max ( f[i-1][j-v] ,max(f[i-1][j-2*v]+1*w , f[i-1][ j - 3*v] +2* w , f[i-1][ j - 4*v] + 3* w , ..... + f[i-1][ j - (k+1)*v] + k* w))
由此可以发现 绿色部分加上一个w ，就等于红色部分
所以公式就可以写为 f[i][j] = max(f[i-1][j] , f[i][j-v]+w)
代码
#include
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N][N];
int main()
{
int n,m;
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][j],f[i][j-v[i]]+w[i]);//注意这里是f[i][j-v[i]]+w[i]，与01背包不同
}
}
cout< （2）一维做法（从前 i 个物品中选，并且体积不超过 j 的最大价值）
公式：f [j] = max( f [ j ] , f [j - v[i]] + w[i])
和上述二维做法类似：1.不选第i件物品（ f [ j ]）
2.选第 i 件物品（f [j - v[i]] + w[i]）
代码
#include
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N];
int main()
{
int n,m;
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=v[i];j<=m;j++)//需要细品和01背包的不同
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout< 我的细品
为什么这里是正序呢？
因为完全背包用的是第 i 行 （也就是当前这一行，而不是01背包，用的是上一行）
前面01背包已经解释了，当正序时候求的就是当前这一行的值，所以用正序。
3.多重背包 （1）小数据范围,时间复杂度 O(n*m*k）有 N 件物品和一个容量是 V 的背包。每件物品有k个。第 i 件物品的体积是 vi，价值是 wi。输出背包可容纳的最大价值。
和01背包类似，只不过多了一重循环
代码
#include
using namespace std;
const int N = 110;
int v[N],w[N],s[N];
int f[N][N];
int main()
{
int n,m;
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] && k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout< 把每种物品，分为log(s)个包裹 ， 就变为01背包问题 ， 这些log(s)个包裹，只有选与不选
如何利用二进制的方法 把每种物品分为log(s)个包裹
such as : 7 （小于7的所有二进制数为 1，2，4），0~7可以用这些二进制表示，且每个数只用一次
0 = 0；
1 = 1；
2 = 2；
3 = 1 + 3；
4 = 4；
5 = 1 + 4；
6 = 2 + 4；
7 = 1 + 2 + 4；
所以 s （1，2 ，4，8，... ，2^k ，c）如果1+2+4+...+2^k < s , 后面需要补一个 c
且2^k+1 一定大于s
代码
#include
using namespace std;
const int N = 15000 , M = 2010;
int v[N],w[N];
int f[M];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(s>=k)
{
cnt++;
v[cnt]=k*a;
w[cnt]=k*b;
s-=k;
k*=2;
}
if(s>0)
{
cnt++;
v[cnt]=s*a;
w[cnt]=s*b;
}
}
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout< 有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
和01背包一样每组选与不选，选的话只能选一个
f[i][j] 表示从前i组中选，体积不超过j的最大值
代码
#include
using namespace std;
const int N = 110;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=0;k=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout< 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）