GZHU18级寒假训练：Cancer's Trial-第六题

HDU-2844

• Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse 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.

• 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

  在网上找到了背包问题的模板：

  有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，每种物品只有一个，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。

int f[w+1];   //f[x] 表示背包容量为x 时的最大价值  
for (int i=0; i<n; i++)  
    for (int j=w; j>=size[i]; j--)  
        f[j] = max(f[j], f[j-size[i]]+value[i]); //逆序 
           

完全背包

如果物品不计件数，就是每个物品有无数件的话，稍微改下即可

for (int i=0; i<n; i++)  
    for (int j=size[i]; j<=w; j++)  
        f[j] = max(f[j], f[j-size[i]]+value[i]);  //正序

           

背包问题定理：

定理：一个正整数n可以被分解成1,2,4,…,2(k-1),n-2k+1（k是满足n-2^k+1>0 的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2(k-1),n-2k+1中某几个数的和的形式。

//看作是体积是M的背包，看最后求出的有几个dp[i]=i的；
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int dp[maxn], A[110], C[110];
int main(){
	int n, m;
	while(scanf("%d%d", &n, &m), n||m){
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++){
			scanf("%d", &A[i]);
		}
		for(int i=1; i<=n; i++){
			scanf("%d", &C[i]);
		}
		for(int i=1; i<=n; i++){
			if(A[i]*C[i]>=m){
				for(int j=A[i]; j<=m; j++){
					dp[j]=max(dp[j], dp[j-A[i]]+A[i]);
				}
			}
			else{
				int k=1;
				while(k<=C[i]){
					for(int j=m; j>=k*A[i]; j--){
						dp[j]=max(dp[j], dp[j-k*A[i]]+k*A[i]);
					}
					C[i]-=k;
					k<<=1;
				}
				for(int j=m; j>=C[i]*A[i]; j--){
					dp[j]=max(dp[j], dp[j-C[i]*A[i]]+C[i]*A[i]);
				}
			}
		}
		int cnt=0;
		for(int i=1; i<=m; i++){
			if(dp[i]==i) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}


           

代码来源：https://blog.csdn.net/Sirius_han/article/details/81207517