大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、0-1背包
1. 有n个重量和价值分别为wi, vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。（1<=n<=100，1<=wi, vi<=100，1<=W<=10000）
样例输入：
4
2 3
1 2
3 4
2 2
5
4
2 1
3 3
4 5
7 9
10
样例输出：
7
12
【分析一】这是最基础、最著名的背包问题。特点是：每种物品仅有一件，可以选择放或不放。（此问题可引申出各种变种，需灵活掌握）。
不妨用子问题定义状态：即dp[i][j]表示前i件物品(部分或全部)恰放入一个容量为j的背包时可以获得的最大价值。则状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}。通过递推完成问题求解。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
解释“将前i件物品放入容量为j的背包中”这个子问题：若只考虑第i件物品放/不放，那么该子问题就可以转化为一个只牵扯前i-1件物品的问题。
① 如果不放第i件物品，问题就转化为“前i-1件物品放入容量为v的背包中”
② 如果放第i件物品，问题就转化为“前i-1件物品放入剩下的容量为j-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值c[i]。
【分析二】空间复杂度的优化
以上方法的时间和空间复杂度均为O(nW)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(W)。
先考虑上面的基本思路如何实现：
肯定是有一个主循环i=1..N，每次算出来二维数组dp[i][0..W]的所有值。那么，如果只用一维数组dp[0..W]，能不能保证第i次循环结束后dp[W]中表示的就是我们定义的状态dp[i][j]呢？
dp[i][j]是由dp[i-1][j]和dp[i-1][j-w[i]]两个子问题递推而来，能否保证在推dp[i][j]时（即在第i次主循环中推dp[j]时）能够得到dp[i-1][j]和dp[i-1][j-w[i]]的值呢？事实上，这要求在每次主循环中我们以j=W..0的逆序推dp[j]，这样才能保证推dp[j]时dp[j-w[i]]保存的是状态dp[i-1][j-w[i]]的值（即结果的“无后效性”）。
代码实现如下：
for(i=1;i<=N;i++)
for(j=W;j>=w[i];j–)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
其中：dp[j]=max{dp[j], dp[j-w[i]]+v[i]}相当于转移方程dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}，因为现在的dp[j-w[i]]就相当于原来的dp[i-1][j-w[i]]。
然而，如果将j的循环顺序从上面的逆序改成顺序的话，那么则成了dp[i][j]由dp[i][j-w[i]]推知，与本题意不符，但它却是另一个重要的完全背包问题最简捷的解决方案，故只用一维数组解01背包问题是十分必要的（特别是数据规模较大的时候，对空间复杂度的优化十分重要）。
【分析三】多组输入，注意数据的初始化。这里使用memset(dp, 0, sizeof(dp)); 表示开始时背包中未放物品，可获得的最大总价值为0。
法一：二维数组解法
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
const int maxn=105; -
const int maxv=10005; -
int N,W; -
int w[maxn],v[maxn]; -
int dp[maxn][maxv]; //dp[i][j]记录前i件物品（部分或全部）放入容量为j的背包中可获得的最大总价值 -
int main() -
{
-
int i,j; -
while(scanf("%d",&N)!=EOF) -
{
-
memset(dp,0,sizeof(dp)); -
for(i=1;i<=N;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
for(i=1;i<=N;i++) -
{
-
for(j=W;j>=1;j--) -
{
-
if(j>=w[i])//放第i件物品，有两种情况 -
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); -
else //不放第i件物品 -
dp[i][j]=dp[i-1][j]; -
} -
} -
printf("%d\n",dp[N][W]); -
} -
return 0; -
}
法二：优化空间复杂度
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
const int maxn=105; -
const int maxv=10005; -
int N,W; -
int w[maxn],v[maxn]; -
int dp[maxv]; //dp[i]记录所选物品总重量不超过i时可获得的最大总价值 -
int main() -
{
-
int i,j; -
while(scanf("%d",&N)!=EOF) -
{
-
memset(dp,0,sizeof(dp)); -
for(i=1;i<=N;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
for(i=1;i<=N;i++) -
for(j=W;j>=w[i];j--) -
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); -
printf("%d\n",dp[W]); -
} -
return 0; -
}
2. 0-1背包升级版
问题情境同上，数据规模：1<=n<=100，1<=wi<=107，1<=vi<=100，1<=W<=109。
【分析】此问题与最初的01背包问题相比，情境相同，只是修改了限制条件的大小。这一次O(nW)的规模就不够用了，不过在这个问题中，相比较重量而言，价值的范围比较小，所以可以试着改变DP的对象。
定义：dp[i+1][j]为前i个物品中挑选出价值总和为j时总重量的最小值。
则dp[0][0]=0,dp[0][j]=INF(不存在就赋值为INF)。
此外，在前i个物品中挑选出价值总和为j时，一定有
前i-1个物品中挑选价值总和为j的部分【即不选第i个物品】
前i-1个物品中挑选价值总和为j-v[i]的部分，然后再选中第i个物品【即选第i个物品】
所以有dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
最终的答案就是令dp[n][j]<=W的最大的j，这样复杂度就变为了O(n∑i vi)。在此题的限制条件下便能完成。
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
const int maxn=105; -
const int maxv=105; -
const int INF=1000000005; -
int n,W; -
int w[maxn],v[maxn]; -
int dp[maxn][maxn*maxv+1]; //dp[i][j]记录前i个物品挑选出价值总和为j时总重量的最小值（不存在时值为无穷大INF） -
int main() -
{
-
int i,j; -
int ret; //ret记录价值总和的最大值 -
while(scanf("%d",&n)!=EOF) -
{
-
for(i=0;i<n;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
for(i=0;i<=maxn*maxv;i++) -
dp[0][i]=INF; -
dp[0][0]=0; //表示前0个物品中什么都挑选不了，故总重量为0（自然最小值也为0） -
for(i=0;i<n;i++) -
{
-
for(j=0;j<=maxn*maxv;j++) -
{
-
if(j<v[i]) //第i件物品的价值比价值总和j还大，则不能选第i件物品 -
dp[i+1][j]=dp[i][j]; -
else //否则可以选也可以不选第i件物品 -
dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]); -
} -
} -
ret=0; -
for(i=0;i<=maxn*maxv;i++) //扫描价值总和，找解 -
{
-
if(dp[n][i]<=W) //n件物品中挑选出的物品价值总和为i时，总重量<=W，则更新ret -
ret=i; -
} -
printf("%d\n",ret); -
} -
return 0; -
}
二、完全背包
有n种重量和价值分别为wi和vi的物品。从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值。在这里，每种物品可以挑选任意多件。
样例输入：
3
3 4
4 5
2 3
7
4
2 1
3 3
4 5
7 9
10
样例输出：
10
12
【分析】这个问题非常类似于上面的0-1背包问题，所不同的是每种物品有任意多件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解0-1背包时的思路，令f[i][j]表示前i种物品恰放入一个容量为j的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i][j]=max{f[i-1][j-k*w[i]]+k*c[i]|0<=k*w[i]<= j}。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明0-1背包问题的方程的确是很重要，可以推及其它类型的背包问题。
这个算法使用一维数组，代码如下：
for(i=1;i<=N;i++)
for(j=w[i];j<=W;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么0-1背包问题中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-w[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-w[i]]。而现在完全背包的特点恰是每种物品可选任意多件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-w[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[i][v]=max{f[i-1][v],f[i][v-w[i]]+c[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。
法一：
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
int n,W; -
int w[105],v[105]; -
int dp[105][10005]; //dp[i][j]记录从前i种物品选一些，放入容量为j的背包中可获得的最大总价值 -
int main() -
{
-
int i,j; -
while(scanf("%d",&n)!=EOF) -
{
-
for(i=1;i<=n;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
memset(dp,0,sizeof(dp)); -
for(i=1;i<=n;i++) -
{
-
for(j=1;j<=W;j++) //注意每种物品可选择任意多件，故应顺序推 -
{
-
if(j>=w[i]) //能放第i件物品的情况 -
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]); -
else //不能放第i件物品的情况 -
dp[i][j]=dp[i-1][j]; -
} -
} -
printf("%d\n",dp[n][W]); -
} -
return 0; -
}
法二：优化空间复杂度
（1）滚动使用二维数组
结合上述递推式：dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);可知dp[i]计算时只需要dp[i-1]和dp[i]，所以可以结合奇偶性，降低二维数组第一维的空间开销。
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
int n,W; -
int w[105],v[105]; -
int dp[2][10005]; //dp[i][j]记录从前i种物品选一些，放入容量为j的背包中可获得的最大总价值 -
int main() -
{
-
int i,j; -
while(scanf("%d",&n)!=EOF) -
{
-
for(i=1;i<=n;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
memset(dp,0,sizeof(dp)); -
for(i=1;i<=n;i++) -
{
-
for(j=1;j<=W;j++) //注意每种物品可选择任意多件，故应顺序推 -
{
-
if(j>=w[i]) //能放第i件物品的情况 -
dp[i&1][j]=max(dp[(i-1)&1][j],dp[i&1][j-w[i]]+v[i]); -
else //不能放第i件物品的情况 -
dp[i&1][j]=dp[(i-1)&1][j]; -
} -
} -
printf("%d\n",dp[n&1][W]); -
} -
return 0; -
}
（2）降低数组维数，使用一位数组
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
int n,W; -
int w[105],v[105]; -
int dp[10005]; -
int main() -
{
-
int i,j; -
while(scanf("%d",&n)!=EOF) -
{
-
for(i=1;i<=n;i++) -
scanf("%d %d",&w[i],&v[i]); -
scanf("%d",&W); -
memset(dp,0,sizeof(dp)); -
for(i=1;i<=n;i++) -
for(j=w[i];j<=W;j++) //顺序推 -
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); -
printf("%d\n",dp[W]); -
} -
return 0; -
}
三、多重背包
例：庆功会
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式：
第一行两个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=10。
输出格式：
一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
样例输入：
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
样例输出：
1040
-
#include <iostream> -
#include <cstdio> -
#include <cstring> -
using namespace std; -
const int maxn=510; -
const int maxm=6010; -
int n,m; -
int v[maxn],w[maxn],s[maxn]; -
int dp[maxm]; //dp[i]:用i元钱购买奖品能获得的最大价值 -
int main() -
{
-
int i,j,k; -
while(scanf("%d %d",&n,&m)!=EOF) -
{
-
for(i=1;i<=n;i++) -
scanf("%d %d %d",&v[i],&w[i],&s[i]); -
memset(dp,0,sizeof(dp)); -
for(i=1;i<=n;i++) //第一重循环枚举奖品种数 -
{
-
for(j=m;j>=0;j--) //第二重循环枚举钱数 -
{
-
for(k=0;k<=s[i];k++) //第三重循环枚举购买某种物品的件数 -
{
-
if(j-k*v[i]>=0) -
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]); -
} -
} -
} -
printf("%d\n",dp[m]); -
} -
return 0; -
}
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/164408.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
