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;} 

后记主要还是为了巩固01背包问题并且多做点题目，所以记录了一下学习《背包九讲》的过程，大家真想搞清楚背包问题，建议还是参考原文链接：http://love-oriented.com/pack/