#include "math.h" #include "stdio.h" #include "string.h" int seekMax(int N, int M, int V[], int W[]); int main(){ int N = 4; //物品的数量 int M = 10; //背包的容量 int V[] = {0,2,4,3,7}; //物品的价值 前面的0就是占位的，方便遍历 int W[] = {0,2,3,5,5}; //物品的重量 int re = seekMax(N, M, V, W); printf("%d", re); } //优化得 int seekMax(int N,int M,int V[],int W[]) { //1、创建dp数组 int dp[M+1]; //2、初始化dp数组 for (int j = 0; j <= M ; j++) { dp[j] = 0; //初始全部都为0 } //3、开始根据状态转移方程地推填满dp数组 for (int i = 1; i <= N; i++) { for (int j = M; j >= W[i]; j--) { dp[j] = fmax(dp[j], dp[j - W[i]] + V[i]); //可以装下，可以选择 拿或者不拿 } } return dp[M]; }
代码： #include "math.h" #include "stdio.h" #include "string.h" int seekMax(int N, int M, int V[], int W[]); int main(){ int N = 2; //物品的数量 int M = 10; //背包的容量 int V[] = {5,8}; //物品的价值 int W[] = {5,7}; //物品的重量 int re = seekMax(N, M, V, W); printf("%d", re); }
//f[i][j]=max(f[i-1][j-k*V[i]]+k*W[i],f[i][j]) 0<=k*c[i]<=j int seekMax(int N,int M,int V[],int W[]) { //1、创建dp数组 int dp[N+1][M+1]; memset(dp, 0, sizeof(dp[0][0]) * (N + 1) * (M + 1)); //先全部置为0，因为c中会给随机值，很烦 //2、初始化dp数组 for (int i = 0; i < N; i++) { dp[i][0] = 0; //背包容量为0，你拿不拿物品价值最大都为0 } for (int j = 0; j < N ; j++) { dp[0][j] = 0; //你不拿物品价值最大都为0 } //3、开始根据状态转移方程地推填满dp数组 for (int i = 0; i < N; i++){ for (int j = 0; j <= M; j++){ for (int k = 0; k * V[i] <= j; k++){ dp[i+1][j] = fmax(dp[i+1][j], dp[i][j-k * V[i]] + k * W[i]); } } } return dp[N][M]; }
3、深入分析理解
这边也可以画出表格来一步一步填这个表格的问题，自底向上，
第一步：初始化时的表格：
第二步：在第 i 个物品的时候，我们其实可以选择上一层中的几个位置中价值最高的那一个，在这里M=10，所以只需要将两个数值进行比较，如果M大于10，那么就需要将取0个、1个和两个i2物品的情况进行比较，然后选出最大值.
#include "math.h" #include "stdio.h" #include "string.h" int seekMax(int N, int M, int V[], int W[]); int main(){ int N = 2; //物品的数量 int M = 10; //背包的容量 int V[] = {0,5,8}; //物品的价值 前面的0就是占位的，方便遍历 int W[] = {0,5,7}; //物品的重量 int re = seekMax1(N, M, V, W); printf("%d", re); } //优化得 int seekMax(int N,int M,int V[],int W[]) { //1、创建dp数组 int dp[M+1]; //2、初始化dp数组 for (int j = 0; j <= M ; j++) { dp[j] = 0; //初始全部都为0 } //3、开始根据状态转移方程地推填满dp数组 for (int i = 1; i <= N; i++) { for (int j = W[i]; j <= M; j++) { dp[j] = fmax(dp[j], dp[j - W[i]] + V[i]); //可以装下，可以选择 拿或者不拿 } } return dp[M]; }
此时时间复杂度 O(N*M） 空间复杂度O(M) 空间复杂度也是变成线性的了。
注解：其实还有一个小优化
比如两件物品 ：ij 当 i 物品的重量比 j 的重，但是 i 的价值确比 j 的低，那我们岂不是可以直接跳过 i 了，直接选择 j 物品了。道理很简单，难道这世界上会有人去买一个又贵又难吃的东西？（富豪除外）
#include "math.h" #include "stdio.h" #include "string.h" int seekMax(int N, int M, int V[], int W[],int n[]); int main(){ int N = 3; //不同物品的数量 int M = 15; //背包的容量 int V[] = {3,4,5}; //物品的价值 int W[] = {2,3,4}; //物品的重量 int n[] = {4, 3, 2};//每种物品的个数 int re = seekMax(N, M, V, W,n); printf("%d", re); } //没有优化的 int seekMax(int N,int M,int V[],int W[],int n[]) { //1、创建dp数组 int dp[N+1][M+1]; memset(dp, 0, sizeof(dp[0][0]) * (N + 1) * (M + 1)); //先全部置为0，因为c中会给随机值，很烦 //2、初始化dp数组 for (int i = 0; i < N; i++) { dp[i][0] = 0; //背包容量为0，你拿不拿物品价值最大都为0 } for (int j = 0; j < N ; j++) { dp[0][j] = 0; //你不拿物品价值最大都为0 } //3、开始根据状态转移方程地推填满dp数组 for (int i = 0; i < N; i++){ for (int j = 0; j <= M; j++){ //k限制了条件 不加限制就是我上面讲的完全背包问题中在我没有优化的时候提出的另外一个方程的解 for (int k = 0; k <= n[i] && k * V[i] <= j; k++){ dp[i+1][j] = fmax(dp[i+1][j], dp[i][j-k * V[i]] + k * W[i]); } } } return dp[N][M]; }
