# 悼念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

Input

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

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

∑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;
}
``````

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

``````#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;
}
``````

# 悼念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

Input

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

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

∑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;
}
``````

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

``````#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;
}
``````