背包问题

有N件物品和一个容量为V的背包，第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

状态转移方程：

f[i][v]=max(f[i−1][v],f[i−1][v−c[i]]+w[i])

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的

伪码如下：

for i=1..N     for v=V..0         f[v]=max{f[v],f[v-c[i]]+w[i]};

如果不放第i件物品，那么问题就转化为”前i−1件物品放入容量为v的背包中”，价值为f[i−1][v]；

如果放第i件物品，那么问题就转化为”前

i−1件物品放入剩下的容量为

v−c[i]的背包中”，此时能获得的最大价值就是

f[i−1][v−c[i]]再加上通过放入第

i件物品获得的价值

w[i]。

例题

Description

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

Input

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

Output

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

Sample Input

70 371 10069 11 2

Sample Output

解题代码1

#include 
     
      using namespace std;int main(){    int T, M;    cin>>T>>M;    int c[101] = {
    0};    int w[101] = {
    0};    for (int i = 1; i <= M; i++)    {        cin>>w[i]>>c[i];    }    int **f = new int*[M + 1];    for (int i = 0; i <= M; i++)    {        f[i] = new int[T + 1];    }    //草药数目为0    for (int i = 0; i <= M; i++)    {        f[i][0] = 0;    }    //采药时间为0    for (int i = 0; i <= T; i++)    {        f[0][i] = 0;    }    int i, j;    for (i = 1; i <= M; i++)    {        for (j = 1; j <= T; j++)        {            if (j >= w[i])            {                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);            }            else            {                f[i][j] = f[i - 1][j];            }        }    }    cout<
      
       <

解题代码2

#include 
     
      using namespace std;int main(){    int T, M;    cin>>T>>M;    int c[101] = {
    0};    int w[101] = {
    0};    for (int i = 1; i <= M; i++)    {        cin>>w[i]>>c[i];    }    int f[1001][101] = {
    0};    for (int i = 1; i <= M; i++)    {        for (int j = 1; j <= T; j++)        {            if (j >= w[i])            {                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);            }            else            {                f[i][j] = f[i - 1][j];            }        }    }    cout<
      
       <

代码2多耗费一些空间，但是代码可以简洁很多。

解题代码3

可以选择使用一维数组来解决该问题，但是值得注意的是，内存循环的顺序必须是V..0，即：

for i=1..N     for v=V..0         f[v]=max{f[v],f[v-c[i]]+w[i]};

如果内层循环为0..V，则实际的状态方程为：

f[i][v]=max(f[i−1][v],f[i][v−c[i]]+w[i])

#include 
     
      using namespace std;int main(){    int T, M;    cin>>T>>M;    int c[101] = {
    0};    int w[101] = {
    0};    for (int i = 1; i <= M; i++)    {        cin>>w[i]>>c[i];    }    int f[101] = {
    0};    for (int i = 1; i <= M; i++)    {        for (int j = T; j >= 1; j--)        {            if (j >= w[i])            {                f[j] = max(f[j], f[j - w[i]] + c[i]);            }        }    }    cout<
      
       <