2013-11-09 20:12:04Morris
[POJ][多重背包] 1742 - Coins
Description
People in
Silverland use coins.They have coins of value A1,A2,A3...An Silverland
dollar.One day Tony opened his money-box and found there were some
coins.He decided to buy a very nice watch in a nearby shop. He wanted to
pay the exact price(without change) and he known the price would not
more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input
The
input contains several test cases. The first line of each test case
contains two integers n(1<=n<=100),m(m<=100000).The second line
contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn
(1<=Ai<=100000,1<=Ci<=1000). The last test case is followed
by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
使用單調隊列加快這一個多重背包問題似乎不錯。
但這裡討論一下，使用 greedy 的思路，在 O(nm) 時間內完成計算。
#include <stdio.h>
#include <string.h>
int main() {
int n, m, i, j;
int a[105], c[105];
char dp[100005];
int q[100005];//greedy
while(scanf("%d %d", &n, &m) == 2 && n) {
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
for(i = 0; i < n; i++)
scanf("%d", &c[i]);
memset(dp, 0, m+1);
dp[0] = 1;
for(i = 0; i < n; i++) {
memset(q, 0, m*4+4);
int r = m-a[i], v = a[i], cap = c[i];
for(j = 0; j <= r; j++) {
if(dp[j] && !dp[j+v] && q[j] < cap) {
dp[j+v] = 1;
q[j+v] = q[j]+1;
}
}
}
int ret = 0;
for(i = 1; i <= m; i++)
ret += dp[i];
printf("%d\n", ret);
}
return 0;
}