NOIP2006普及組 開心的金明 happy 解題報告

【問題描述】

金明今天很開心，家裏購置的新房就要領鑰匙了，新房裏有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎 麼佈置，你說了算，只要不超過 N 元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分爲 5 等：用整數 1 ~ 5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第 j 件物品的價格爲 v[j] ，重要度爲 w[j] ，共選中了 k 件物品，編號依次爲 j1 ， j2 ，……， jk ，則所求的總和爲：

v[j1]*w[j1]+v[j2]*w[j2]+ … +v[jk]*w[jk] 。（其中 * 爲乘號）

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

【輸入格式】

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

N m

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

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

v p

（其中 v 表示該物品的價格 (v<=10000) ， p 表示該物品的重要度 (1~5) ）

【輸出格式】

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

【輸入輸出樣例】

輸入：

1000 5

800 2

400 5

300 5

400 3

200 2

輸出：

3900

【分析】

本題和NOIP2006提高組第二題——金明的預算方案形成對應。都是同一類型、同一背景的題。
這是個典型的、簡單的0/1背包問題，
F[i,k]表示前i件物品花費最大為k時 物品價格與物品重要度乘積的最大值。
W[i]表示第i件物品的價格。
V[i]表示第i件物品的重要度。
狀態轉移方程：
F[i,k]=    F[i-1,k] (W[i]>k)
              F[i,k]=max{ F[i-1,k], F[i-1,k-W[i]]+W[i]*V[i]}  (W[i]<=k)
邊界條件：
(數組下標從1開始)
F[1][k]=W[i]*V[i] (W[i]>=k)

【我的代碼】

 #include <iostream>
using namespace std;
int TolM;//總錢數
int TolThing;//總物品
int F[26][100001];
class THING
{
public:
    int v;//價格
    int p;//重要度
}T[25];

int getval(int i)
{
    return (T[i].v*T[i].p);
}

void init()
{
    cin>>TolM>>TolThing;
    for (int i=1;i<=TolThing;i++)
    {
        cin>>T[i].v>>T[i].p;
    }
    fclose(stdin);
    return;
}

void predp()
{
    int i,j;
    for (i=1;i<=TolThing;i++)
        for (j=1;j<=TolM;j++)
            F[i][j]=0;
   
    int q=getval(1);
    for (i=T[1].v;i<=TolM;i++)
    {
        F[1][i]=q;
    }
    return;
}

void print()
{
    int i,j;
    for (i=1;i<=TolThing;i++)
    {
        for (j=1;j<=TolM;j++)
            cout<<F[i][j]<<" ";
        cout<<endl;   
    }
    cout<<endl;
}

void dp()
{
    int i,j;
    for (i=2;i<=TolThing;i++)
    {
        for (j=1;j<=TolM;j++)
        {
            if (T[i].v>j)
                F[i][j]=F[i-1][j];
            else
                F[i][j]=
                ((F[i-1][j])>(F[i-1][j-T[i].v]+getval(i))?
                (F[i-1][j]):(F[i-1][j-T[i].v]+getval(i)));
        }
    }
}

int main()
{
    freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
    init();
    predp();
    dp();
    //print();
    cout<<F[TolThing][TolM]<<endl;
    return 0;
}

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

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