NOIP2006提高組 金明的預算方案 budget 解題報告

【問題描述】

金明今天很開心，家裏購置的新房就要領鑰匙了，新房裏有一間金明自己專用的很 寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行”。今天一早 ， 金明就開始做預算了，他把想買的物品分爲兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：

主件	附件
電腦	打印機，掃描儀
書櫃	圖書
書桌	檯燈，文具
工作椅	無

如果要買歸類爲附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分爲 5 等：用整數 1 ~ 5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是 10 元的整數倍）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第 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 ] 。（其中 * 爲乘號）

請你幫助金明設計一個滿足要求的購物單。

 【輸入文件】

輸入文件的第 1 行，爲兩個正整數，用一個空格隔開：N m

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

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

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

【輸出文件】

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

【輸入樣例】

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

【輸出樣例】

2200

【分析】

以下題解來自BYVoid大牛的網誌：

http://www.byvoid.com/blog/noip-allsolutions/

動態規劃。背包問題的衍生問題。

首先把附件物品分離出來，歸爲主件所有。於是每次決策成了5種

1、不購買

2、購買主件

3、購買主件 + 附件 1

4、購買主件 + 附件 2

5、購買主件 + 附件 1 + 附件 2

由於題中所述每件物品都是整10元，可以加一個小小的優化，就是每個物品的價格除以10。最後結果在乘以10輸出。

狀態設定

F[i,j] 前i個主件，花費爲j元的時候，重要程度與價格乘積的總和的最大值

V[i] 第i個主件的價格

W[i] 第i個主件的重要程度

狀態轉移方程

F[i,j] =

Max

{

F[ i - 1 , j ], (不購買)

F[ i - 1 , j - V[i] ] + V[i] * W[i], (只購買主件)

F[ i - 1 , j - V[i] - V[i的附件1] ] + V[i] * W[i] + V[i的附件1] * W[i的附件1], (購買主件+附件1)

F[ i - 1 , j - V[i] - V[i的附件2] ] + V[i] * W[i] + V[i的附件2] * W[i的附件2], (購買主件+附件2)

F[ i - 1 , j - V[i] - V[i的附件1] - V[i的附件2] ] + V[i] * W[i] + V[i的附件1] * W[i的附件1] + V[i的附件2] * W[i的附件2], (購買主件+附件1+附件2)

}

邊界條件

F[0,k]=0 (0<=k<=N)

目標結果

F[M,N]

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned short int usint;
usint N,m,M;//N:總錢數,m:總物品數,M:主件數
usint F[60][3200];//F[i,j]=前i個物品，花費為j時的最大 價格×重要值

class MAIN
{
public:
    usint num;//該物品的編號
    usint mprice;//主件的花費
    usint mvalue;//主件的重要度
    bool a;//是否有附件1
    usint aprice;//附件1的價格
    usint avalue;//附件1的重要度
    bool b;//是否有附件2
    usint bprice;//附件2的價格
    usint bvalue;//附件2的重要度
    MAIN()
    {
        a=false;
        b=false;
        aprice=avalue=bprice=bvalue=0;
    }
}T[60];

void init()
{
    cin>>N>>m;
    N/=10;
    int v,p,q;
    for (usint i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v,&p,&q);
        v/=10;
        if (q==0)
        {
            M++;
            T[M].num=i;
            T[M].mprice=v;
            T[M].mvalue=p;
            continue;
        }
        if (q>0)
        {
            for (usint j=1;j<=M;j++)
            {
                if (T[j].num==q)
                {
                    if (!T[j].a)
                    {
                        T[j].a=true;
                        T[j].aprice=v;
                        T[j].avalue=p;
                        break;
                    }
                    else if (T[j].a)
                    {
                        T[j].b=true;
                        T[j].bprice=v;
                        T[j].bvalue=p;
                        break;
                    }
                }
            }
        }
    }
    return;
}

void dp()
{
    usint i,j,f;
    for (i=0;i<=M;i++)
        F[0][i]=0;
   
    for (i=1;i<=M;i++)
    {
        for (j=1;j<=N;j++)
        {
            usint maxn=0;
            //不買
            if (F[i-1][j]>maxn)
                maxn=F[i-1][j];
           
            //只買主件
            if (j>=T[i].mprice)
            {
                f=F[i-1][j-T[i].mprice]+T[i].mprice*T[i].mvalue;
                if (f>maxn)
                    maxn=f;
            }
           
            //買主件+附件1
            if (T[i].a && j>= (T[i].mprice+T[i].aprice) )
            {
                f=F[i-1][j-T[i].mprice-T[i].aprice]+
                T[i].mprice*T[i].mvalue+T[i].aprice*T[i].avalue;
                if (f>maxn)
                    maxn=f;
            }
           
            //買主件+附件2
            if (T[i].b && j>= (T[i].mprice+T[i].bprice) )
            {
                f=F[i-1][j-T[i].mprice-T[i].bprice]+
                T[i].mprice*T[i].mvalue+T[i].bprice*T[i].bvalue;
                if (f>maxn)
                    maxn=f;
            }
           
            //買主件+附件1+附件2
            if (T[i].a && T[i].b && j>=(T[i].mprice+T[i].aprice+T[i].bprice) )
            {
                f=F[i-1][j-T[i].mprice-T[i].aprice-T[i].bprice]+
                T[i].mprice*T[i].mvalue+
                T[i].aprice*T[i].avalue+T[i].bprice*T[i].bvalue;
                if (f>maxn)
                    maxn=f;
            }
           
            F[i][j]=maxn;
        }
    }
}

int main()
{
    freopen("budget.in","r",stdin);
    freopen("budget.out","w",stdout);
    init();
    //print();
    dp();
    cout<<F[M][N]*10<<endl;
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.033 s	648 KB	0
2	正确	10	0.001 s	648 KB	0
3	正确	10	0.001 s	648 KB	0
4	正确	10	0.001 s	648 KB	0
5	正确	10	0.001 s	648 KB	0
6	正确	10	0.001 s	648 KB	0
7	正确	10	0.001 s	648 KB	0
8	正确	10	0.002 s	648 KB	0
9	正确	10	0.003 s	648 KB	0
10	正确	10	0.001 s	648 KB	0

运行完成
运行时间 0.043 s
平均内存使用 648 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!