01背包、完全背包、多重背包
前言今天花了一下午加一晚上的时间，在九度oj才ac了一道简单的多重背包题目，之前没做过多重背包的题目，导致我做题时复杂化了，虽然是假期但是也不能这么浪费时间，果断总结一下，这里参考了dd_engi大牛的《背包问题九讲》，原文链接：http://love-oriented.com/pack/
01背包
题目有N件物品和一个容量为V的背包。第i建物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大
思路这是最基础的背包问题，特点是：每种物品只有一件，可以选择放或者不放
用子问题定义状态：即dp[i][j]表示前i件物品放入一个容量为j的背包可以获得的最大价值。则其状态转移方程为：
#include <stdio.h>#include <stdlib.h> typedef struct rice { int price, weight, num;} rice; void dynamic(rice *rices, int m, int n){ int i, j, cur, k, **dp; // 动态申请二维数组 dp = (int **)malloc(sizeof(int *) * (m + 1)); for (i = 0; i <= m; i ++) dp[i] = (int *)malloc(sizeof(int) * (n + 1)); // 初始化 for (i = 0; i <= m; i ++) for (j = 0; j <= n; j ++) dp[i][j] = 0; // 动态规划 for (i = 1; i <= m; i ++) { for (j = 1; j <= n; j ++) { for (k = 0; k <= rices[i].num; k ++) { if (j - k * rices[i].price >= 0) { cur = dp[i - 1][j - k * rices[i].price] + k * rices[i].weight; dp[i][j] = dp[i][j] > cur ? dp[i][j] : cur; } else { break; } } } } printf("%d\n", dp[m][n]); for (i = 0; i <= m; i ++) free(dp[i]);} int main(void){ int i, c, n, m; rice rices[2010]; scanf("%d", &c); while (c --) { scanf("%d %d", &n, &m); // 接收数据 for (i = 1; i <= m; i ++) { scanf("%d %d %d", &rices[i].price, &rices[i].weight, &rices[i].num); } // 多重背包问题 dynamic(rices, m, n); } return 0;}