先推荐个视频

b站算法训练营

一、类型1，重量限制

题目：

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

输入：

输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。

以后N行每行两个数Wi和Vi,表示物品的重量和价值

其中数据规模和约定：1<=N<=200,M<=5000.

输出：

输出1行，包含一个整数，表示最大价值。

思路1二维数组

1. 思路：

动态规划问题

打表

找动态转换方程

dp[i][j]表示背包容量为j，第i个物品时的最大价值

i表示从物品1到物品i；j表示背包容量为j

我们可以从第一个物品开始，求出j=1到10时的最大价值

再找第二个物品，从j=1到10时的最大价值

再找第三个物品......

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

2、二维数组代码：

#include
#include
#include
using namespace std;
int n, m;
int weight[210], value[210];
int dp[210][5010];
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> weight[i] >> value[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (weight[i] <= j) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}elsedp[i][j] = dp[i - 1][j];}}cout << dp[n][m];return 0;
}

思路2一维数组

1. 思路

从上面的表可以看出，第i个物品时，求最大价值只与i-1个物品时最大价值有关，所以可以用一维数组dp[j]来表示背包容量为j时的最大价值。

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

之所以倒推是因为，递推关系是用i-1来推出的i，所以求i时，i-1还在。

如果正推，那就是用新的i推出新的i，就变成了多次取第i个物品

正推图：

2. 代码

#include
#include
#include
using namespace std;
int n, m;
int weight[210], value[210];
int dp[5010];
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> weight[i] >> value[i];}for (int i = 1; i <= n; i++) {for (int j = m; j >=weight[i]; j--) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[m];return 0;
}

二、类型2，重量和体积限制

题目：

有5件物品，它们分别有价值，体积和重量。

为了把它们装进一个背包里，其体积和重量必须符合要求，不超过背包要求的容量。

请问背包内装物品，其最大价值是多少。

输入：

第一行是两个数，V，W（V,W<=10000），表示背包可负载的最大体积和重量

输入包括5行。

每行都包含三个数字，pi，vi，wi，(pi,vi,wi<=10000)表示价值，体积和重量。

输出：

包括一个数，表示可装下的最大价值。

思路：

数据较少，可直接枚举

时间复杂度2^5

每件物品只有两种状态，0（不拿）、1（拿）

代码：

#include
#include
#include
using namespace std;
int v, w,pr,vo,we,mx;
int price[6], volume[6],weight[6];
int dp[6];
void func(int u) {if (u <= 5) {dp[u] = 0;func(u + 1);dp[u] = 1;func(u + 1);}else {pr = 0; vo = 0; we = 0;for (int i = 1; i <= 5; i++) {pr += price[i] * dp[i];vo += volume[i] * dp[i];we += weight[i] * dp[i];}if (pr > mx && vo <= v && we <= w) {mx = pr;}}
}
int main() {cin >> v >> w;for (int i = 1; i <= 5; i++) {cin >> price[i] >> volume[i] >> weight[i];}func(1);cout << mx << endl;return 0;
}