1. 01背包
问题描述：
有n件物品和一个容量为v的背包。放入第i件物品的占的空间为Ci,得到的价值是Wi,求解将哪些物品装入背包可以
使得总价值最大；
首先要明白这个问题不能用贪心来做，因为当前的选择会影响到以后的选择，也就是说当前的选择的最优解
可能会影响到全局的最优解；
考虑用动态规划来做
1.定义状态：
定义状态dp[i][j]为前i件物品恰放入容量为j的背包时的最大价值；
那么dp[n][v]就是这个问题的最终解；
2.描述不同状态如何转移：
在这个过程中，我们很自然想到的决策就是第i件物品放还是不放；放与不放会直接影响到dp[i][j]的值；
1.放，那么dp[i][j]的状态可由dp[i-1][j-Ci] + Wi转移过来
2.不放，那么dp[i][j]的状态可由dp[i-1][j]转移过来
我们所要做的就是在这两种决策中选取一种最优的；
所以状态转移方程为dp[i][j] = max(dp[i-1][j-Ci] + Wi , dp[i-1][j]);
3.按一个方向求出该问题的解
状态dp[i][j]总是要取决于之前的状态dp[i-1][j-Ci] + Wi,dp[i-1][j],所以我们应按按自底而上的方向求解
当然，除了这种状态，我们可以定义另外一种状态来解决01背包问题
1.定义状态：
定义状态dp[i][j]为前i个物品中价值为j时的耗费的最小空间；
2.描述不同状态如何转移：
在这个过程中，我们能够很自然的想到当前物品的选与不选会影响当前状态；
1.放，那么状态dp[i][j]的状态可由状态dp[i-1][j-W[i]] + C[i]转移过来
2.不放，那么状态dp[i][j]的状态可由状态dp[i-1][j]转移过来
所以状态转移方程为dp[i][j] = min(dp[i-1][j-W[i] + C[i] , dp[i-1][j]);
3.自底而上的求解
注意初始化，dp[0][0]为[0],dp[0][j]为不合法的状态，用一个无穷大的数代替；
在把所有状态求出来之后，我们只需要找出dp[n][j]不大于V的最大j值即可
两种不同状态的代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 2005;
int dp[INF][INF]; //定义状态dp[i][j]为前i件物品放入容量为j的背包时的最大价值；
int W[INF],C[INF];
int main()
{
int n, v;
scanf("%d%d",&n,&v);
for(int i = 1; i <= n; i++)
{
scanf("%d",&W[i]);
}
for(int i = 1; i <= n; i++)
{
scanf("%d",&C[i]);
}
memset(dp,0,sizeof(dp)); //初始化
for(int i = 1; i <= n; i++) //自底而上的求解
{
for(int j = 0; j <= v; j++)
{
if(j >= C[i])
{
dp[i][j] = max(dp[i-1][j],dp[i-1][j - C[i]] + W[i]); //状态转移
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n",dp[n][v]);
return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 2005;
int dp[INF][INF]; //定义状态dp[i][j]为前i个物品中价值为j时的耗费的最小空间；
//这种状态只适用于C[i]的值很大，而W[i]的值较小的情况
int W[INF],C[INF];
int main()
{
int T;
scanf("%d",&T);
int n, v;
scanf("%d%d",&n,&v);
for(int i = 1; i <= n; i++)
{
scanf("%d",&W[i]);
}
for(int i = 1; i <= n; i++)
{
scanf("%d",&C[i]);
}
memset(dp,0,sizeof(dp)); //初始化
for(int i = 1; i < INF; i++)
{
dp[0][i] = INF + 5;
}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= INF; j++)
{
if(j >= W[i])
{
dp[i][j] = min(dp[i-1][j],dp[i-1][j - W[i]] + C[i]); //状态转移方程
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
int res = -1;
for(int j = 0; j < INF; j++)if(dp[n][j] <= v) //根据定义的状态可得结果是dp[n][j]不大于V的最大j值即可
{
res = j;
}
printf("%d\n",res);
return 0;
}
01背包代码在时间上不能被优化，但在空间上可以优化，具体如何优化，这里不再讲解，想了解的自行百度
————————————————————————————————————————————————————
2.完全背包
问题描述：
有n种物品和一个容量为v的背包，每种物品都有无限件可用，放入第i种物品的费用是Ci,价值是Wi;问如何装才能使
总价值最大；
仔细看这个问题，会发现这个问题和01背包类似，01背包是有n种物品，每种只有1件；所以我们可以根据01背包
的策略来做；
定义状态dp[i][j]为前i种物品恰放入容量为j的背包时的最大价值；
在01背包中，对于每一种物品来说，策略是取0件或是取1件。在完全背包中，对于每一种物品来说，相关的策略是
取0件，取1件，取2件，取3件......取v/Ci(知道背包装不下为止)，类比01背包，我们所要做的就是在这些策略选择一
个最优的；
所以这个状态转方程为：
dp[i][j] = max(dp[i-1][j-k*Ci] + k*Wi) k*Ci <= v;
这种方法的代码为：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;
int dp[INF][INF]; //定义状态dp[i][j]为前i件物品恰放入容量为j的背包时的最大价值；
int main()
{
int n,v;
while(~scanf("%d%d",&n,&v))
{
int W[INF + 5],C[INF + 5];
for(int i = 1; i <= n; i++)
{
scanf("%d %d",&C[i],&W[i]);
}
mmset(dp,0); //初始化
for(int i = 1; i <= n; i++) //自底而上的求解
{
for(int j = 0; j <= v; j++)
{
if(j >= C[i])
{
for(int k = 1; k * C[i] <= j; k++)
{
dp[i][j] = max(dp[i][j],dp[i-1][j-k*C[i]] + k*W[i]); //状态转移方程
}
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n",dp[n][v]);
}
return 0;
} 但是这种方法的时间复杂度比较高，所以考虑一下更好的方法；
在上面中，策略是对于第i种物品，有取0件，取1件，取2件，取v/C[i]件。仔细想一下这个过程，我们就会发现
对于每个dp[i][j],我们都要在从取1件开始，直到取到v/C[i]件。为什么要从取1件开始呢，因为我们不确定dp[i][j]
的值从取第几件转移过来是最大的。所以我们要从取第1件开始试，一直试到放不下背包为止；
我们再看一下是如何定义状态的，dp[i][j]是指 前i件物品恰放入容量为j的背包时的最大价值，注意两个词，"恰",
"最大价值"，
这说明dp[i][j]是指在空间为j的背包中，不能再装下任意一个前i种物品时，背包所能拥有的最大价值（仔细理解
一下这句话，对接下来推导的状态转移方程有很大帮助）。
所以对于dp[i][j]来说，如果只放1件第i种物品就能使dp[i][j]最大，那么一定是在dp[i][j - C[i]]的基础上放的.
换句话说dp[i][j]是dp[i][j - ci]多放一件i物品转移过来的
那么我们只需要在放不放这件物品进行决策，所以状态转移方程为：
dp[i][j] = max(dp[i][j - C[i]] + W[i], dp[i-1][j]); (有点绕，不懂的可以多想想)；
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;
int dp[INF][INF]; //定义状态
int main()
{
int n,v;
while(~scanf("%d%d",&n,&v))
{
int W[INF + 5],C[INF + 5];
for(int i = 1; i <= n; i++)
{
scanf("%d %d",&C[i],&W[i]);
}
mmset(dp,0); //初始化
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= v; j++)
{
if(j >= C[i])
{
dp[i][j] = max(dp[i][j-C[i]] + W[i],dp[i-1][j]); //状态转移方程
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n",dp[n][v]);
}
return 0;
} 这个代码时间上很难在优化了，空间上可以优化，这里不再讲解，自己思考或者百度。
————————————————————————————————————————————————————
3.多重背包：
问题描述：
有n种物品和一个容量为v的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci,价值是Wi。求解：
如何装才能使背包价值最大。
仍然先把它转化为01背包来做。时间复杂度是O(n*v*(n*Mi)),时间复杂度是比较高的。
考虑是否能优化：
转化为01背包的思路是，第i种物品有Mi个，我们把这第i种物品的Mi个当成01背包来做。我们需要一件一件
的放第i种物品，为什么要一件一件的放呢？(注意，这是优化的关键)，因为我们在放第Mi件物品时，必须要
从前Mi-1件转移过来，如果没有前Mi-1件物品，我们就无法得到前Mi件物品的最优解。同理，在求前Mi-1
的最优解，必须从前Mi-2转移过来。干说有些枯燥，我们来举个例子说明一下；
有1种物品，共7件。一个空间为8的背包，每件物品耗费的空间是1，价值是1。问如何装才能使背包价值最大
定义状态为dp[i][j]为前i件物品恰放入空间为j的背包时的最大价值。
我们可以用一个图表来表示求这个问题时，dp[i][j]的变化：
可以看出dp[i]主要是比dp[i-1]多了蓝色部分；看出dp[2][2]是从dp[1][1]转移过来的
dp[3][3]是从dp[2][2]转移过来的；dp[4][4]是从dp[3][3]转移过来的.........
如果没有dp[2]，那么dp[3]的状态能求出来吗？（可以自己思考一下）
从dp[2]到dp[3]转移是放了一件物品，既然没有dp[2],我们可以在dp[1]上放2件物品来转移到dp[3]；
（注意，这点就相当于理解优化的关键）；
注意：可能有人会这样想，直接在dp[1]上加上6件物品，求这样出dp[7]这样会更快。但是这样是错的；
如果放6件物品，dp[7][2]只能从dp[1][-4]转移过来，显然是不合理的。
经过以上分析，我们意识到把一种物品拆分成多个物品时可行的。
我们可以用二进制的思想拆分物品，把个数为Mi个的物品拆分为
2^0, 2^1,2^2.......2^n, Mi - (2^(n+1)-1)个物品；
那么7就可以被分解为个数为1,2,4的物品；
如图
这就是拆分成多个物品的转移过程；
下图是拆分成多个物品后的dp[i][j]的状态
可以看出这个表的1，2，4行分别对应上表的1，3，7行；
可以发现我们把一个物品拆分成若干个二的次幂，可以使得后面的区间不重不漏的从前面转移过来；
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;
int dp[INF][INF]; //定义状态
int n,v,count1 = 1;
void ZeroPack(int w,int c);
int main()
{
int W[INF],C[INF],M[INF];
scanf("%d%d",&n,&v);
for(int i = 1; i <= n; i++)
{
scanf("%d %d %d",&W[i],&C[i],&M[i]);
}
mmset(dp,0); //初始化
for(int i = 1; i <= n; i++)
{
int k = 1;
int num = M[i];
while(k < num) //二进制拆分物品
{
ZeroPack(W[i] * k,C[i] * k);
num -= k;
k <<= 1;
}
ZeroPack(W[i] * num,C[i] * num) ;
}
printf("%d\n",dp[count1-1][v]);
return 0;
}
void ZeroPack(int w,int c)
{
for(int j = 0; j <= v; j++)
{
if(j >= c)
{
dp[count1][j] = max(dp[count1-1][j],dp[count1-1][j - c] + w);
}
else
{
dp[count1][j] = dp[count1-1][j] ;
}
}
count1++;
}
这个代码可以在空间上优化，也能在时间上优化；
时间上优化主要是当Ci * Mi >= v，这时候该种物品一定可以装满背包，可以这种物品看成完全背包来做；
空间上优化不再赘述；
————————————————————————————————————————————————————
————————————————————————————————————————————————————
至此，三种基础背包已经讲解完毕，但是还有一些细节上的问题需要注意：
关于背包有两种不同的问法：
第一种是：求背包的最大价值，上面讲的就是这个问题；
第二种是：求背包在装满的时候的最大价值；
关于第二种问法，我们只需要在初始化的时候，把dp[0][0]赋值为0，其他的dp[0][1~v]赋值为-OO(负无穷);
可以这样理解：
初始化的dp数组就是在没有装任何物品的合法状态。如果要求背包恰好装满，那么显然，只有容量为0的背包
是合法状态，因为他能满足当没有一件物品装入背包时“恰好装满”,其他的容量为1~v的背包都不满足，所以
是非法状态，用-OO表示；
如果只是要求背包的最大价值，并没有求装满，那么在初始化的时候dp[0][0~v]可以什么都不装，而且都是
合法状态，所以dp[0][0~v]初始化为0；
————————————————————————————————————————————————————
————————————————————————————————————————————————————
下面是三种背包空间优化过后的代码(主要是利用了滚动数组，这里只给出代码，不再讲解，请自行百度)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 10005;
int dp[INF];
int n,v; //物品的种类和背包的容量
void ZeroPack(int w,int c) ; //01背包
void CompletePack(int w,int c); //完全背包
void MultiplePack(int w,int c,int m) ; //多重背包
int main()
{
int W[INF],C[INF],M[INF]; //物品的价值，耗费的空间，件数
scanf("%d %d",&n,&v);
for(int i = 1; i <= n; i++)
{
scanf("%d %d %d",&W[i],&C[i],&M[i]);
}
mmset(dp,0); //注意初始化要根据问法不同而改变
for(int i = 1; i <= n; i++)
{
if(M[i] == 1) //属于01背包
{
ZeroPack(W[i],C[i]);
}
else if(C[i] * M[i] >= v) //属于完全背包
{
CompletePack(W[i],C[i]);
}
else //多重背包
{
MultiplePack(W[i],C[i],M[i]) ;
}
}
printf("%d\n",dp[v]);
return 0;
}
void ZeroPack(int w,int c)
{
for(int j = v; j >= c; j--)
{
dp[j] = max(dp[j],dp[j - c] + w);
}
}
void CompletePack(int w,int c)
{
for(int j = c; j <= v; j++)
{
dp[j] = max(dp[j],dp[j - c] + w);
}
}
void MultiplePack(int w,int c,int m)
{
if(c * m >= v)
{
CompletePack(w,c);
}
else
{
int k = 1;
while(k < m)
{
ZeroPack(w*k,c*k);
m -= k;
k <<= 1;
}
ZeroPack(w*m,c*m);
}
}
京公网安备 11010502036488号