HDU 2191 悼念512汶川大地震遇難同胞——珍惜現在,感恩生活 多重揹包

NO IMAGE

悼念512汶川大地震遇難同胞——珍惜現在,感恩生活

                                                                    Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768
K (Java/Others)
                                                                                          Total Submission(s): 23022    Accepted Submission(s): 9725


Problem Description
急!災區的食物依然短缺!
為了挽救災區同胞的生命,心繫災區同胞的你準備自己採購一些糧食支援災區,現在假設你一共有資金n元,而市場有m種大米,每種大米都是袋裝產品,其價格不等,並且只能整袋購買。
請問:你用有限的資金最多能採購多少公斤糧食呢?

後記:
人生是一個充滿了變數的生命過程,天災、人禍、病痛是我們生命歷程中不可預知的威脅。
月有陰晴圓缺,人有旦夕禍福,未來對於我們而言是一個未知數。那麼,我們要做的就應該是珍惜現在,感恩生活——
感謝父母,他們給予我們生命,撫養我們成人;
感謝老師,他們授給我們知識,教我們做人
感謝朋友,他們讓我們感受到世界的溫暖;
感謝對手,他們令我們不斷進取、努力。 
同樣,我們也要感謝痛苦與艱辛帶給我們的財富~


 


Input
輸入資料首先包含一個正整數C,表示有C組測試用例,每組測試用例的第一行是兩個整數n和m(1<=n<=100, 1<=m<=100),分別表示經費的金額和大米的種類,然後是m行資料,每行包含3個數p,h和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
 


Author
lcy
 


Source
 


Recommend
lcy   |   We have carefully selected several similar problems for you:  1203 1160 2059 1421 1158 
 

點選開啟題目連結

多重揹包,下面的分析參照揹包九講

方法一:轉化為01揹包

n[i] 表示第 i 種物品的個數,V 為揹包容量

把第 i 種物品換成 n[i] 件01揹包中的物品,則得到了物品數為
∑n[i] 的01揹包問題,直接求解,複雜度是O(V * ∑n[i])。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100   10;
int pri[MAXN], wei[MAXN], num[MAXN];
int dp[MAXN], t, sum, n;
void solve()
{
scanf("%d", &t);
while (t--)
{
memset(dp, 0, sizeof(dp));
scanf("%d%d", &sum, &n);
for (int i = 1; i <= n; i  ) scanf("%d%d%d", &pri[i], &wei[i], &num[i]);
for (int i = 1; i <= n; i  )            ///n種大米
{
for (int j = 1; j <= num[i]; j  )     ///第i種大米的袋數
{
for (int k = sum; k >= pri[i]; k--) ///揹包容量
{
dp[k] = max(dp[k], dp[k - pri[i]]   wei[i]);    ///狀態轉移方程
}
}
}
printf("%d\n", dp[sum]);
}
}
int main()
{
solve();
return 0;
}

方法二:01揹包 完全揹包

這裡用二進位制的思想,我們把第 i 種物品換成若干件物品,使得原問題中第 i 種物品可取的每種策略——取1,2…n[i] 件

——均能等價於取若干件代換以後的物品。另外,取超過 n[i] 件的策略必不能出現。

將第 i 種物品分成若干件物品,其中每件物品有一個係數,這件物品的費用和價值均是原來的費用和價值乘以這個係數,

使這些係數分別為 1,2,4,…,2^(k-1),n[i]-2^k 1,且 k 是滿足n[i]-2^k 1>0的最大整數。例如,如果n[i]為13,就將這種物品分成係數分別為1,2,4,6 的四件物品。

分成的這幾件物品的係數和為n[i],表明不可能取多於n[i]件的第 i 種物品,另外這種方法也能保證對於1..n[i]間的每一個整數,均可以用若干個係數的和表示,這個證明可以分1..2^k-1和2^k..n[i]兩段來分別討論得出,並不難,希望你自己思考嘗試一下。

這樣就將第 i 種物品分成了O(log n[i])種物品,將原問題轉化為了複雜度為O(V*∑log n[i])的01揹包問題,是很大的改進。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100   10;
int pri[MAXN], wei[MAXN], num[MAXN];
int dp[MAXN], t, sum, n;
void zeroOnePack(int price, int weight, int sum)    ///01揹包
{
for (int i = sum; i >= price; i--)
dp[i] = max(dp[i], dp[i - price]   weight);
}
void completePack(int price, int weight, int sum)   ///完全揹包
{
for (int i = price; i <= sum; i  )
dp[i] = max(dp[i], dp[i - price]   weight);
}
void multiPack(int n, int sum)          ///多重揹包
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i  )
{
if (pri[i] * num[i] > sum)      ///只買第i種大米可以將經費花完
completePack(pri[i], wei[i], sum);  ///轉化為完全揹包
else
{
for (int k = 1; k < num[i]; k *= 2) ///轉化為01揹包,係數為1,2,4...2^(k-1)
{
zeroOnePack(k * pri[i], k * wei[i], sum);
num[i] -= k;
}
if (num[i] != 0)    ///最後剩餘的袋數(num[i]-2^k 1)
zeroOnePack(num[i] * pri[i], num[i] * wei[i], sum);
}
}
printf("%d\n", dp[sum]);
}
void solve()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &sum, &n);
for (int i = 1; i <= n; i  ) scanf("%d%d%d", &pri[i], &wei[i], &num[i]);
multiPack(n, sum);
}
}
int main()
{
solve();
return 0;
}

由於本題的資料不算大,這兩種方法的耗時沒有太大差距。
還有用單調佇列優化的O(VN)的方法,研究中。。。

悼念512汶川大地震遇難同胞——珍惜現在,感恩生活

                                                                    Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768
K (Java/Others)
                                                                                          Total Submission(s): 23022    Accepted Submission(s): 9725


Problem Description
急!災區的食物依然短缺!
為了挽救災區同胞的生命,心繫災區同胞的你準備自己採購一些糧食支援災區,現在假設你一共有資金n元,而市場有m種大米,每種大米都是袋裝產品,其價格不等,並且只能整袋購買。
請問:你用有限的資金最多能採購多少公斤糧食呢?

後記:
人生是一個充滿了變數的生命過程,天災、人禍、病痛是我們生命歷程中不可預知的威脅。
月有陰晴圓缺,人有旦夕禍福,未來對於我們而言是一個未知數。那麼,我們要做的就應該是珍惜現在,感恩生活——
感謝父母,他們給予我們生命,撫養我們成人;
感謝老師,他們授給我們知識,教我們做人
感謝朋友,他們讓我們感受到世界的溫暖;
感謝對手,他們令我們不斷進取、努力。 
同樣,我們也要感謝痛苦與艱辛帶給我們的財富~


 


Input
輸入資料首先包含一個正整數C,表示有C組測試用例,每組測試用例的第一行是兩個整數n和m(1<=n<=100, 1<=m<=100),分別表示經費的金額和大米的種類,然後是m行資料,每行包含3個數p,h和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
 


Author
lcy
 


Source
 


Recommend
lcy   |   We have carefully selected several similar problems for you:  1203 1160 2059 1421 1158 
 

點選開啟題目連結

多重揹包,下面的分析參照揹包九講

方法一:轉化為01揹包

n[i] 表示第 i 種物品的個數,V 為揹包容量

把第 i 種物品換成 n[i] 件01揹包中的物品,則得到了物品數為
∑n[i] 的01揹包問題,直接求解,複雜度是O(V * ∑n[i])。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100   10;
int pri[MAXN], wei[MAXN], num[MAXN];
int dp[MAXN], t, sum, n;
void solve()
{
scanf("%d", &t);
while (t--)
{
memset(dp, 0, sizeof(dp));
scanf("%d%d", &sum, &n);
for (int i = 1; i <= n; i  ) scanf("%d%d%d", &pri[i], &wei[i], &num[i]);
for (int i = 1; i <= n; i  )            ///n種大米
{
for (int j = 1; j <= num[i]; j  )     ///第i種大米的袋數
{
for (int k = sum; k >= pri[i]; k--) ///揹包容量
{
dp[k] = max(dp[k], dp[k - pri[i]]   wei[i]);    ///狀態轉移方程
}
}
}
printf("%d\n", dp[sum]);
}
}
int main()
{
solve();
return 0;
}

方法二:01揹包 完全揹包

這裡用二進位制的思想,我們把第 i 種物品換成若干件物品,使得原問題中第 i 種物品可取的每種策略——取1,2…n[i] 件

——均能等價於取若干件代換以後的物品。另外,取超過 n[i] 件的策略必不能出現。

將第 i 種物品分成若干件物品,其中每件物品有一個係數,這件物品的費用和價值均是原來的費用和價值乘以這個係數,

使這些係數分別為 1,2,4,…,2^(k-1),n[i]-2^k 1,且 k 是滿足n[i]-2^k 1>0的最大整數。例如,如果n[i]為13,就將這種物品分成係數分別為1,2,4,6 的四件物品。

分成的這幾件物品的係數和為n[i],表明不可能取多於n[i]件的第 i 種物品,另外這種方法也能保證對於1..n[i]間的每一個整數,均可以用若干個係數的和表示,這個證明可以分1..2^k-1和2^k..n[i]兩段來分別討論得出,並不難,希望你自己思考嘗試一下。

這樣就將第 i 種物品分成了O(log n[i])種物品,將原問題轉化為了複雜度為O(V*∑log n[i])的01揹包問題,是很大的改進。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100   10;
int pri[MAXN], wei[MAXN], num[MAXN];
int dp[MAXN], t, sum, n;
void zeroOnePack(int price, int weight, int sum)    ///01揹包
{
for (int i = sum; i >= price; i--)
dp[i] = max(dp[i], dp[i - price]   weight);
}
void completePack(int price, int weight, int sum)   ///完全揹包
{
for (int i = price; i <= sum; i  )
dp[i] = max(dp[i], dp[i - price]   weight);
}
void multiPack(int n, int sum)          ///多重揹包
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i  )
{
if (pri[i] * num[i] > sum)      ///只買第i種大米可以將經費花完
completePack(pri[i], wei[i], sum);  ///轉化為完全揹包
else
{
for (int k = 1; k < num[i]; k *= 2) ///轉化為01揹包,係數為1,2,4...2^(k-1)
{
zeroOnePack(k * pri[i], k * wei[i], sum);
num[i] -= k;
}
if (num[i] != 0)    ///最後剩餘的袋數(num[i]-2^k 1)
zeroOnePack(num[i] * pri[i], num[i] * wei[i], sum);
}
}
printf("%d\n", dp[sum]);
}
void solve()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &sum, &n);
for (int i = 1; i <= n; i  ) scanf("%d%d%d", &pri[i], &wei[i], &num[i]);
multiPack(n, sum);
}
}
int main()
{
solve();
return 0;
}

由於本題的資料不算大,這兩種方法的耗時沒有太大差距。
還有用單調佇列優化的O(VN)的方法,研究中。。。