Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 48043 Accepted Submission(s): 20489
Problem Description
急！災區的食物依然短缺！
為了挽救災區同胞的生命，心系災區同胞的你準備自己采購一些糧食支援災區，現在假設你一共有資金n元，而市場有m種大米，每種大米都是袋裝産品，其價格不等，并且隻能整袋購買。
請問：你用有限的資金最多能采購多少公斤糧食呢？
Input
輸入資料首先包含一個正整數 C C C，表示有 C C C組測試用例，每組測試用例的第一行是兩個整數 n n n和 m ( 1 < = n < = 100 , 1 < = m < = 100 ) m(1<=n<=100, 1<=m<=100) m(1<=n<=100,1<=m<=100),分别表示經費的金額和大米的種類，然後是m行資料，每行包含3個數p，h和 c ( 1 < = p < = 20 , 1 < = h < = 200 , 1 < = c < = 20 ) c(1<=p<=20,1<=h<=200,1<=c<=20) c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的價格、每袋的重量以及對應種類大米的袋數。
Output
對于每組測試資料，請輸出能夠購買大米的最多重量，你可以假設經費買不光所有的大米，并且經費你可以不用完。每個執行個體的輸出占一行。
Sample Input
1
8 2
2 100 4
4 100 2
Sample Output
400
解題思路
分析：其實這就是多重背包，但會發現用最赤裸裸的方法是過不了的，連二進制優化也都不行。那下面就來介紹一下用單調隊列來實作的時間複雜度為 O ( n m ) O(nm) O(nm)的多重背包。
很顯然前兩個循環是少不了的，那麼我們來想如何去掉第三個循環，進而使時間複雜度變為我們想要的 O ( n m ) O(nm) O(nm)。
若 w [ i ] w[i] w[i]表示物品重量， v [ i ] v[i] v[i]表示價值， c [ i ] c[i] c[i]表示數量，我們知道樸素狀态轉移方程：
令 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − k ∗ w [ i ] ] + k ∗ v [ i ] ) f[i][j] = max(f[i][j],f[i-1][j-k*w[i]] + k*v[i]) f[i][j]=max(f[i][j],f[i−1][j−k∗w[i]]+k∗v[i]) ( 1 < = k < = c [ i ] ) (1 <= k <= c[i]) (1<=k<=c[i]) 這裡的 k k k 是指取第 i i i 種物品 k k k 件。
如果令 a = j / w [ i ] a = j / w[i] a=j/w[i] （a為最多能選多少個i物品）, b = j %w[i] 那麼 j = a ∗ w [ i ] + b j = a * w[i] + b j=a∗w[i]+b.
這裡用 k k k 表示的意義改變， k k k 表示取第 i i i 種物品的件數比 a a a 少幾件。
現在我們枚舉 b b b，也就是餘數，我們按餘數來分層，不同層之間不能互相轉移。
那麼 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ b + k ∗ w [ i ] ] − k ∗ v [ i ] ) + a ∗ v [ i ] ) f[i][j] = max(f[i][j] ,f[i-1][b+k*w[i]] - k*v[i]) + a*v[i]) f[i][j]=max(f[i][j],f[i−1][b+k∗w[i]]−k∗v[i])+a∗v[i])
可以發現， f [ i − 1 ] [ b + k ∗ w [ i ] ] − k ∗ v [ i ] f[i-1][b+k*w[i]] - k*v[i] f[i−1][b+k∗w[i]]−k∗v[i] 隻與 k k k 有關，而這個 k k k是一段連續的。我們要做的就是求出 f [ i − 1 ] [ b + k ∗ w [ i ] ] − k ∗ v [ i ] f[i-1][b+k*w[i]] - k*v[i] f[i−1][b+k∗w[i]]−k∗v[i] 在 k k k 取可行區間内時的最大值。
代碼
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int t,n,m,w,v,s,h,T,c,f[10010],q[10010],num[10010];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&w,&v,&s);
s=min(s,m/w);
for(int d=0;d<w;d++)//為前文的b，也就是餘數
{
h=1,t=1;
for(int j=0;j<=(m-d)/w;j++)//為前文的k
{
int y=f[j*w+d]-v*j;
while(h<t&&q[t-1]<=y)--t;
q[t]=y,num[t++]=j;
while(h<t&&j-num[h]>s)++h;
f[j*w+d]=max(f[j*w+d],q[h]+v*j);
}
}
}
printf("%d\n",f[m]);
memset(f,0,sizeof(f));
memset(q,0,sizeof(q));
memset(num,0,sizeof(num));
}
}