題目描述

王強(qiáng)今天很開心，公司發(fā)給N元的年終獎。王強(qiáng)決定把年終獎用于購物，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

主件 附件
電腦 打印機(jī)，掃描儀
書柜 圖書
書桌 臺燈，文具
工作椅 無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬于自己的附件。王強(qiáng)想買的東西很多，為了不超出預(yù)算，他把每件物品規(guī)定了一個重要度，分為 5 等：用整數(shù) 1 ~ 5 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是 10 元的整數(shù)倍）。他希望在不超過 N 元（可以等于 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設(shè)第 j 件物品的價格為 v[j] ，重要度為 w[j] ，共選中了 k 件物品，編號依次為 j 1 ， j 2 ，……， j k ，則所求的總和為：
v[j 1 ]w[j 1 ]+v[j 2 ]w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 為乘號）
請你幫助王強(qiáng)設(shè)計(jì)一個滿足要求的購物單。

2.輸入輸出

輸入描述:
輸入的第 1 行，為兩個正整數(shù)，用一個空格隔開：N m

（其中 N （ <32000 ）表示總錢數(shù)， m （ <60 ）為希望購買物品的個數(shù)。）

從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數(shù)據(jù)，每行有 3 個非負(fù)整數(shù) v p q

（其中 v 表示該物品的價格（ v<10000 ）， p 表示該物品的重要度（ 1 ~ 5 ）， q 表示該物品是主件還是附件。如果 q=0 ，表示該物品為主件，如果 q>0 ，表示該物品為附件， q 是所屬主件的編號）

輸出描述:
輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（ <200000 ）。

3.解題思路

此題目可先化簡為分組背包問題，再求解.

4.源碼實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 有條件分組背包問題(購物單問題)
 * p = 5
 * h = (800, 2, 0), (400, 5, 1), (300, 5, 1), 
 *     (400, 3, 0), (500, 2, 0)
 * w = (800,  1200, 1100, 1500), ( 400), ( 500)
 * v = (1600, 3600, 3100, 5100), (1200), (1000)
 * c = 1000
 */

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    /*int w[61][11] = {{0, 0}, {4,  80,   120,  110,  150}, {1,   40}, {1,   50}};
    int v[61][11] = {{0, 0}, {4, 1600, 3600, 3100, 5100}, {1, 1200}, {1, 1000}};*/
    int w[61][11];
    int v[61][11];
    int u[61][3201];
    int m[61][3201];
    int h[3][61];
    int b[61][51];
    int d[61];
    int g[61];
    int x[61];
    int t[5];
    int r[61][10][4];
    int n = 3;
    int s = 0;
    int c = 100;
    int z = 0;
    int l;
    int i, j, k;

    j = 1;

    memset(m, 0x00, sizeof(m));
    memset(u, 0x00, sizeof(u));
    memset(r, 0x00, sizeof(r));
    memset(w, 0x00, sizeof(w));
    memset(v, 0x00, sizeof(v));

    scanf("%d %d", &c, &s);

    c /= 10;

    for(i=1; i<=s; i++)
    {
        scanf("%d %d %d", &h[0][i], &h[1][i], &h[2][i]);

        if(!h[2][i])
        {
            b[j][0] = i;        /*第j個組的主件的行數(shù)*/
            d[i] = j;           /*第i行屬于哪個組*/
            j++;                /*組數(shù)量+1*/
        }
        else
        {
            t[0] = h[2][i];     /*附件屬于哪一行的主件*/
            t[1] = d[t[0]];     /*主件屬于哪一個組*/
            g[t[1]]++;          /*組元素加一*/
            t[2] = g[t[1]];     /*組元素編號*/
            b[t[1]][t[2]] = i;  /*組中的附件編號所屬行數(shù)*/
        }
    }

    l = j - 1;                  /*組個數(shù)*/

    /*(for(i=1; i<=l; i++)
    {
        for(j=0; j<=g[i]; j++)
        {
            printf("b[%d][%d]=%d ", i, j, b[i][j]);
        }

        printf("\n");
    }*/

    for(i=1; i<=l; i++)
    {
        /*無附件情況*/
        t[0] = 1;
        t[1] = b[i][0];                             /*組中的主件所屬行數(shù)*/
        w[i][t[0]] = h[0][t[1]] / 10;               /*主件價格*/
        v[i][t[0]] = h[1][t[1]] * h[0][t[1]];       /*主件目標(biāo)權(quán)重*/
        r[i][t[0]][0] = 1;                          /*第i組第幾種排列方式*/

        t[0]++;

        /*一種附件情況*/
        for(j=1; j<=g[i]; j++)
        {
            t[1] = b[i][0];
            t[2] = b[i][j];

            r[i][t[0]][0] = 1;
            r[i][t[0]][j] = t[1];

            w[i][t[0]] = (h[0][t[1]] + h[0][t[2]]) / 10;
            v[i][t[0]] = h[1][t[1]] * h[0][t[1]] + h[1][t[2]] * h[0][t[2]];

            t[0]++;
        }

        /*兩種附件情況*/
        for(j=1; j<=g[i]; j++)
        {
            for(k=j+1; k<=g[i]; k++)
            {
                t[1] = b[i][0];
                t[2] = b[i][j];
                t[3] = b[i][k];

                r[i][t[0]][0] = 1;
                r[i][t[0]][j] = 1;
                r[i][t[0]][k] = 1;

                w[i][t[0]] = (h[0][t[1]] + h[0][t[2]] + h[0][t[3]]) / 10;
                v[i][t[0]] = h[1][t[1]] * h[0][t[1]] + h[1][t[2]] * h[0][t[2]] + h[1][t[3]] * h[0][t[3]];

                t[0]++;
            }
        }

        w[i][0] = t[0] - 1;
        v[i][0] = w[i][0];
    }

    /*for(i=1; i<=l; i++)
    {
        for(k=1; k<=w[i][0]; k++)
        {
            printf("w[%d][%d]=%d\n", i, k, w[i][k]);
        }
    }*/

    n = l;

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=c; j++)
        {
            z = m[i-1][j];

            for(k=1; k<=w[i][0]; k++)
            {
                if(j >= w[i][k])
                {
                    m[i][j] = max(z, m[i-1][j-w[i][k]]+v[i][k]);

                    if(m[i][j] > z)
                    {
                        u[i][j] = k;
                        z = m[i][j];
                    }
                }
                else
                {
                    m[i][j] = z;
                }
            }
        }
    }

    /*for(i=1; i<=n; i++)
    {
        for(j=1; j<=c; j++)
        {
            printf("%d\t", m[i][j]);
        }

        printf("\n");
    }*/

    printf("%d\n", m[n][c]);

    for(i=n; i>=1; i--)
    {
        if(u[i][c])
        {
            x[i] = u[i][c];
            c -= w[i][x[i]];
        }
        else
        {
            x[i] = 0;
        }
    }

    /*for(i=1; i<=n; i++)
    {
        printf("%d\t", x[i]);
    }

    printf("\n");*/

    return 0;
}

5.編譯源碼

$ gcc -o example examle.c -std=c89

6.運(yùn)行及其結(jié)果

$ ./example
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200