首页 > 代码库 > POJ3624(背包问题)

POJ3624(背包问题)

  1、题目链接地址

  http://poj.org/problem?id=3624

  2、源代码

#include<iostream>using namespace std;#define MAXN 3403 //物品的最大数量#define MAXM 12881 //重量的上限 int max(int x, int y){    if (x > y) return x;    else return y;} int main(){    int n, m; //n:个数,m:不能超过的重量    while(cin >> n >> m && n && m)    {        int i, v;        int w[MAXN] = {0}; //重量        int d[MAXN] = {0}; //需要程度        int dp[MAXM] = {0};         for (i = 1; i <= n; i++)        cin >> w[i] >> d[i];        for (i = 1; i <= n; i++)//重点位置        {            for (v = m; v >= w[i]; v--)            dp[v] = max(dp[v], dp[v - w[i]] + d[i]);        }        cout << dp[m] << endl;    }    return 0;}

  3、分析

    这个题的背包的承重量为m,物品的个数为n,物品的重量w[],物品的需要程度d[],dp[]辅助数组.

    以上面的数据为例

    4 6 //物品的个数为4, 背包的称重量为6

    1 4 //重量为1,需要程度4

    2 6 //重量为2,需要程度6

    3 12 //重量为3,需要程度12

    2 7 //重量为2,需要程度7

    对于第一物品的作出决定的时候

    i = 1, v = 6, dp[6] = max(dp[6], dp[5] + d[1]) = max(0, 0 + 4) = 4;

    i = 1, v = 5, dp[5] = max(dp[5], dp[5 - w[1] + d[1]) = max(0,dp[4] +4) = 4;

    一直算,有如下的结果:

i\v

1

2

3

4

5

6

1

4

4

4

4

4

4

2

4

6

10

10

10

10

3

4

6

12

16

18

22

4

4

7

12

16

19

23