[動態規劃]NOIP模擬題：逛街 shop 解題報告

【問題描述】

某天，zcL在街上閒逛。他在超市裏看到促銷廣告：商品大降價。於是他很高興地拿着籃子購物去了。

已知商場內有n種商品。每種商品的重量爲w千克，價格爲v，價值爲t。此種商品有h件。

注意：此商場有一個奇怪的規定。每種物品要麼不買，要麼買1件或h件。ZCL帶了y元。ZCL最多能扛x千克的物品。請幫ZCL求出他最多能獲得的價值。(不允許搶劫)

【輸入】

輸入文件shop.in的第一行有3個用空格隔開的整數n、x和y。

接下來的n行，每行有4個數據，分別爲w，v，t和h。

【輸出】

輸出文件shop.out共一行，表示ZCL最多能獲得的價值。

【輸入輸出樣例】

shop.in

2 8 10

5 3 7 1

3 7 10 1

shop.out。

17

【限制】

100％的數據滿足：0≤n≤300．0≤x≤1000，0≤y≤100，0≤h≤10

【分析】

這是一個多維的0/1背包問題，動態規劃。

由於這個背包有三維，所以開三維數組會爆掉的。

我們可以採取邊讀邊算的方式把數組降為二維。

狀態設定

     F[i,j] 重量為i千克，花費為j元時的最大價值。

邊界條件

     F[i,j]=0 （0<=i<=x,0<=j<=y）

狀態轉移方程

     F[i,j]=Max{F[i,j] , F[i-w,j-v]+t , F[i-w*h,j-v*h]+t*h}

目標結果：

     F[x][y]

【我的代碼】

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int N;
int X,Y;
int W,V,T,H;
int F[1001][101];

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

int main()
{
    freopen("shop.in","r",stdin);
    freopen("shop.out","w",stdout);
    scanf("%d %d %d\n",&N,&X,&Y);
   
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d %d %d\n",&W,&V,&T,&H);
        for (int i=X;i>=W;i--)
        {
            for (int j=Y;j>=V;j--)
            {
                F[i][j]=Max(F[i][j],F[i-W][j-V]+T);
                if(i-W*H>=0 && j-V*H>=0)
                    F[i][j]=Max(F[i][j],F[i-W*H][j-V*H]+T*H);
            }
        }
    }
   
    printf("%d\n",F[X][Y]);
    return 0;
}