UVa 10130 SuperSale
題意：
某超市進行大特賣，每一種商品都有超低優惠價格，但一個人在每種商品最多只能拿一樣、且每個人有負重上限，現在有一個家族要去搶購，要你求出這個家族在每個人的負重限制下，所能拿的商品最高價值和是多少
題目給出T筆測資(1 <= T <= 1000)，N代表有幾種商品(1 <= N <= 1000)，接下來N列每列有兩個數字：P和W(1 <= P <= 100, 1 <= W <= 30)，第i列的資料代表第i種商品的價值和重量，接下來一列只含一個數字G(1 <= G <= 100)，代表家族的人數，接下來G列每列只含一個數字，第i列的數字代表第i人的負重上限
解題思路：
典型背包問題，只是現在是好幾個人要拿東西，就相當於考慮好幾個背包裝東西，針對每個人不同的負重上限，分別套一次解背包問題的演算法，把結果總和起來就是答案
code：
某超市進行大特賣，每一種商品都有超低優惠價格，但一個人在每種商品最多只能拿一樣、且每個人有負重上限，現在有一個家族要去搶購，要你求出這個家族在每個人的負重限制下，所能拿的商品最高價值和是多少
題目給出T筆測資(1 <= T <= 1000)，N代表有幾種商品(1 <= N <= 1000)，接下來N列每列有兩個數字：P和W(1 <= P <= 100, 1 <= W <= 30)，第i列的資料代表第i種商品的價值和重量，接下來一列只含一個數字G(1 <= G <= 100)，代表家族的人數，接下來G列每列只含一個數字，第i列的數字代表第i人的負重上限
解題思路：
典型背包問題，只是現在是好幾個人要拿東西，就相當於考慮好幾個背包裝東西，針對每個人不同的負重上限，分別套一次解背包問題的演算法，把結果總和起來就是答案
code：
留言
張貼留言