完全背包笔记
内容
完全背包
问题描述
已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
条件:每种物品都有无限件，能放多少就放多少。
问题:在不超过背包容量的情况下，最多能获得多少价值或收益
[hermit auto=”1″ loop=”0″ unexpand=”0″ fullheight=”0″]songlist#:1768956938[/hermit]
举例：物品个数N = 3，背包容量为V = 5，则背包可以装下的最大价值为40.
基本思路
1.直接扩展01背包
由于本问题类似于01背包问题，在01背包问题中，物品要么取，要么不取，而在完全背包中，物品可以取0件、取1件、取2件…直到背包放不下位置。因此，可以直接在01背包的递推式中扩展得到。
f[i][v]:表示前i件物品放入容量为v的容量中时的最大收益
递推式：
f[i][v] = max(f[i – 1][v],f[i – K * weight[i]] + K * Value[i]); 其中 1 <= K * weight[i] <= v,(v指此时背包容量)
//初始条件
f[0][v] = 0;
f[i][0] = 0;
代码
#include <iostream>
#include <assert.h>
using namespace std;
/*
f[i][v]:前i件物品放入背包容量为v的背包获得的最大收益
f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Wi] + k * Vi,其中 1<=k<= v/Wi)
边界条件
f[0][v] = 0;
f[i][0] = 0;
*/
const int N = 3;
const int V = 5;
int weight[N + 1] = {0,3,2,2};
int Value[N + 1] = {0,5,10,20};
int f[N + 1][V + 1] = {0};
int Completeknapsack()
{
//边界条件
for (int i = 0;i <= N;i++)
{
f[i][0] = 0;
}
for (int v = 0;v <= V;v++)
{
f[0][v] = 0;
}
//递推
for (int i = 1;i <= N;i++)
{
for (int v = 1;v <= V;v++)
{
f[i][v] = 0;
int nCount = v / weight[i];
for (int k = 0;k <= nCount;k++)
{
f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);
}
}
}
return f[N][V];
}
int main()
{
cout<<Completeknapsack()<<endl;
return 1;
}
复杂度分析
程序需要求解N*V个状态，每一个状态需要的时间为O（v/Weight[i]），总的复杂度为O(NV*Σ(V/c[i]))。
代码优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。
即，如果一个物品A是占的地少且价值高，而物品B是占地多，但是价值不怎么高，那么肯定是优先考虑A物品的。
这里代码略。
2.转化为01背包
思路 1、
完全背包的物品可以取无限件，根据背包的总容量V和第i件物品的总重量Weight[i],可知，背包中最多装入V/Weight[i](向下取整)件该物品。因此可以直接改变第i件物品的总个数，使之达到V/Weight[i](向下取整)件，之后直接利用01背包的思路进行操作即可。
举例：物品个数N = 3，背包容量为V = 5。
拆分之前的物品序列：
（图片来自网络）
根据上述思想：在背包的最大容量（5）中，最多可以装入1件物品一，因此不用扩展物品一。最多可以装入2件物品二，因此可以扩展一件物品二。同理，可以扩展一件物品三。
时间复杂度的分析：O（NNew*V），其中V表示扩展前背包容量，NNew表示扩展后物品的个数，NNew = Σ(V/Weight[i](向下取整))
思路 2、
对物品进行拆分时，拆成二进制的形式。
具体思路：把第i种物品拆成费用为weight[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足weight[i]*2^k<=V。
思路：这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。
这样把每种物品拆成O(log V/weight[i])件物品，是一个很大的改进。
举例：物品个数N = 3，背包总容量为V = 5。
拆分之前的物品序列：
为了和前面的例子保持一致，这里才用之前的例子，但是这个例子没有更好的说明二进制的拆分方法拆分的物品个数会少写。
假设物品A的重量为2，收益为3，背包的总重量为20。
根据第一种拆分，可以拆成10个物品，每一个物品的重量为2，收益为3。
根据第二种拆分方法，可以拆成4个物品，分别是物品一（重量为1*2，收益为3），物品二（重量为2*2，收益为6），物品三（重量为4*2，收益为12），物品四（重量为8*2，收益为24）。
时间复杂度的分析：O（NNEW*V），其中V表示扩展前背包容量，NNew表示扩展后物品的个数，NNew = Σ(log V/weight[i](向下取整))
代码
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
/*
f[v]:表示第i件物品放入容量为v的背包后，获得的最大容量
f[v] = max(f[v],f[v - weight[i]] + value[i]);
初始条件：f[0] = 0;
*/
const int N = 3;
const int V = 20;//5
int weight[N + 1] = {0,3,2,2};
int Value[N + 1] = {0,5,10,20};
int NNew = 0;
vector<int> weightVector;
vector<int> Valuevector;
int f[V + 1] = {0};
/*拆分物品*/
void SplitItem()
{
//从1开始
weightVector.push_back(0);
Valuevector.push_back(0);
//开始拆分
int nPower = 1;
for (int i = 1;i <= N;i++)
{
nPower = 1;
while (nPower * weight[i] <= V)
{
weightVector.push_back(nPower * weight[i]);
Valuevector.push_back(nPower * Value[i]);
nPower <<= 1;
}
}
}
int Completeknapsack()
{
//拆分物品
SplitItem();
//转化为01背包处理
NNew = weightVector.size() - 1;//多加了一个0，要减去
for (int i = 1;i <= NNew;i++)//物品个数变化
{
for (int v = V;v >= weightVector[i];v--)//背包容量仍是V
{
f[v] = max(f[v],f[v - weightVector[i]] + Valuevector[i]);
}
}
return f[NNew];
}
int main()
{
cout<<Completeknapsack()<<endl;
return 1;
}
3.顺序的01背包
伪代码
for (int i = 1;i <= N;i++)
{
for (int v = weight[i];v <= V;v++)
{
f[v] = max(f[v],f[v – weight[i]] + Value[i]);
}
}
分析：这和01背包的伪代码很相似，在01背包的代码中，v变化的区间是逆序循环的，即[V,Weight[i]]。而这里，v变化的区间是顺序循环的，即为[Weight[i],V]。
原因
再次给出定义：
f[i][v]表示把前i件物品放入容量为v的背包时的最大代价。
f[i-1][v-c[i]]表示把前i – 1件物品放入容量为v的背包时的最大代价.
在01背包中，v变化的区间是逆序循环的原因：要保证由状态f[i-1][v-c[i]]递推状态f[i][v]时，f[i-1][v-c[i]]没有放入第i件物品。之后，在第i循环时，放入一件第i件物品。
01背包的方程：
f[i][v] = max(f[i – 1][v],f[i – 1][v – weight[i]] + Value[i])
在完全背包中，v变化的区间是顺序循环的原因：完全背包的特点是每种物品可选无限件，在求解加选第i种物品带来的收益f[i][v]时，在状态f[i][v-c[i]]中已经尽可能多的放入物品i了，此时在f[i][v-c[i]]的基础上，我们可以再次放入一件物品i，此时也是在不超过背包容量的基础下，尽可能多的放入物品i。
完全背包的方程：
f[i][v] = max(f[i – 1][v],f[i][v – weight[i]] + Value[i]);
举个栗子：
当i = 2，我们要求 f [5]：表示检测物品2放入容量为5的背包的最大收益
上图表示，当i = 2，求f[5]时f数组的状况，
橙色为数组现在存储的值，这些值是i = 1时(上一次循环)存入数组 f 的。相当于f[i – 1][v]
而黄色使我们要求的值，在求f[5]之前，f[5]= 5，即f[i – 1][5] = 5
现在要求 i = 2 时的f[5] = f[5 – 2] + 10 = 5 + 10 = 15 > f[i – 1][5] = 5
故，f[5] = 15；
注意一点，在求f[v]时，它引用的 f[v – weight[i]] 和 f[v]都是上一次循环的结果
当i = 2，我们要求 f [5]：表示检测物品2放入容量为5的背包的最大收益
上图表示，当i = 2，求f[5]时f数组的状况，
橙色为数组现在存储的值，这些值是i = 2时(本次循环)存入数组 f 的。相当于f[i][v]
这是由于，我们是增序遍历数组f的，在求f[v]时，v之前的值(0 ~ v – 1)都已经在第i次循环中求出。
而黄色使我们要求的值，在求f[5]之前，f[5]= 5，即f[i – 1][5] = 5
现在要求 i = 2 时的f[5] = f[5 – 2] + 10 =10+ 10 = 20 > f[i – 1][5] = 5
故，f[5] = 20；
其中引用的f[3]是相当于f[i][3] 而不是正常的f[i – 1][3]
注意一点，在求f[v]时，它引用的 f[v – weight[i]]是本次循环的结果 而f[v]是上一次循环的结果
换个角度说，
在检测 背包容量为5时，看物品2是否加入
由状态转移方程可知，我们f[5]需要引用自己本身和f[3]
由于背包容量为3时，可以装入物品2，且收益比之前的大，所以放入背包了。
在检测f[5]时，肯定要加上物品2的收益，而f[5]在引用f[3]时，f[3]时已经加过一次物品2，
因此，在枚举背包容量时，物品2会加入多次。
代码
二维数组
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
const int N = 3;
const int V = 5;//5
int weight[N + 1] = {0,3,2,2};
int Value[N + 1] = {0,5,10,20};
int f[N + 1][V + 1] = {0};
int Completeknapsack()
{
//初始化
for (int i = 0;i <= N;i++)
{
f[i][0] = 0;
}
for (int v = 0;v <= V;v++)
{
f[0][v] = 0;
}
for (int i = 1;i <= N;i++)
{
for (int v = weight[i];v <= V;v++)
{
f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
}
}
return f[N][V];
}
int main()
{
cout<<Completeknapsack()<<endl;
return 1;
}
代码
一维背包
include <iostream>
using namespace std;
const int N = 3;
const int V = 5;//5
int weight[N + 1] = {0,3,2,2};
int Value[N + 1] = {0,5,10,20};
int f[V + 1] = {0};
int Completeknapsack()
{
f[0] = 0;
for (int i = 1;i <= N;i++)
{
for (int v = weight[i];v <= V;v++)
{
f[v] = max(f[v],f[v - weight[i]] + Value[i]);
}
}
return f[V];
}
int main()
{
cout<<Completeknapsack()<<endl;
return 1;
}