25 | 动态规划（下）：背包问题与动态规划算法优化

听了这几次课，感觉对动态规划的理解又上了一个台阶，比如状态定义的维度分析。我们每个人都有一个装知识的小桶，桶底有小窟窿，老师正好给了我几个堵洞的石头，感谢。

作业感觉只要初始化一个w和v数组就可以呀。。。 #include<stdio.h> #define MAX_N 100 #define MAX_V 10000 int v[MAX_N + 5] = {10,20,20,7,14,7,12,12,8,16,32}, w[MAX_N + 5] = {4,8,8,3,6,3,12,12,9,18,36}; int dp[MAX_N + 5][MAX_V + 5]; int get_dp(int n, int W) { // 初始化 dp[0] 阶段 for (int i = 0; i <= W; i++) dp[0][i] = 0; // 假设 dp[i - 1] 成立，计算得到 dp[i] // 状态转移过程，i 代表物品，j 代表背包限重 for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { // 不选择第 i 种物品时的最大值 dp[i][j] = dp[i - 1][j]; // 与选择第 i 种物品的最大值作比较，并更新 if (j >= w[i] && dp[i][j] < dp[i - 1][j - w[i]] + v[i]) { dp[i][j] = dp[i - 1][j - w[i]] + v[i]; } } } return dp[n][W]; } int main(){ int a; a = get_dp(5,25); printf("%d",a); }

茶艺师学编程 多重背包问题 最多装37元，其中是3个镀金极客币，和1个胡船长手办。 在这里体会到，要玩好数组，要留意下标，不然就只算出34。 /*多重背包*/ #include <stdio.h> #define MAX_N 100 #define MAX_V 10000 int v[12] = {0, 10, 20, 20, 7, 14, 7, 12, 12, 8, 16, 32}; int w[12] = {0, 4, 8, 8, 3, 6, 3, 12, 12, 9, 18, 36}; int dp[MAX_N + 5][MAX_V + 5]; int s[12]; int get_dp(int n, int W) { // 初始化 dp[0] 阶段 for (int i = 0; i <= W; i++) dp[0][i] = 0; // 假设 dp[i - 1] 成立，计算得到 dp[i] // 状态转移过程，i 代表物品，j 代表背包限重 for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { // 不选择第 i 种物品时的最大值 dp[i][j] = dp[i - 1][j]; s[i] = {0}; // 与选择第 i 种物品的最大值作比较，并更新 if (j >= w[i] && dp[i][j] < dp[i - 1][j - w[i]] + v[i]) { dp[i][j] = dp[i - 1][j - w[i]] + v[i]; s[i] = {1}; } } } return dp[n][W]; } int main(){ printf("最多能装%d元\n", get_dp(11, 15)); puts("\n 其中的组合为：\n"); if(s[1] == 1)puts("1个镀金极客币，4kg每个，价值 10 块钱"); if(s[2] == 1)puts("2个镀金极客币，8kg每个，价值 20 块钱"); if(s[3] == 1)puts("2个镀金极客币，8kg每个，价值 20 块钱"); if(s[4] == 1)puts("1个胡船长手办，3kg每个，价值 7 块钱"); if(s[5] == 1)puts("2个胡船长手办，6kg每个，价值 14 块钱"); if(s[6] == 1)puts("1个胡船长手办，3kg每个，价值 7 块钱"); if(s[7] == 1)puts("1个西瓜，12kg每个，价值 12 块钱"); if(s[8] == 1)puts("1个西瓜，12kg每个，价值 12 块钱"); if(s[9] == 1)puts("1个哈密瓜，9kg每个，价值 8 块钱"); if(s[10] == 1)puts("2个哈密瓜，18kg每个，价值 16 块钱"); if(s[11] == 1)puts("4个哈密瓜，36kg每个，价值 32块钱"); return 0; }