coins
Problem Description
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
题意：给你一些一定面额 一定数量的硬币，让你求用这些硬币中的一些能组成多少种不同的总价值
刚开始想暴力遍历所有情况，后大致看了一下题解，发现是个动态规划问题
为什么是动规？动态规划不是只能求最优解吗？这是求所有的可能性啊！
看了下题解后的理解。
怎样运用动规求解：
首先将dp数组初始化，dp[0]=0;其余全部设为-INF,
为什么要这么做：dp[i]表示总额为i的状态，在加入某枚硬币时，使 i-weight==0时，说明总额为i 这情况有可能产生
此时需要把这个状态标记，怎样标记：
dp[i]=max{dp[i],dp[i-weight]+value} ,若i-weight==0，则dp[i]=0 (这样就把该状态标记了，这也是为什么让dp[0]=0了)
否则dp[i]=-INF( 当 i-weight！= 0，即总额为 i 的情况不可能发生的时候 ，dp[i] 永远为-INF ， 这也是为什么 其余全部设为-INF )
看了别人代码，也有不从初始化方面下手的，只是改了最后的判断条件，if（dp[i]==i）ans++;
这样改判断条件是很好懂了，但状态转移方程怎么理解？（不懂）
说完初始化，
接下来分析题目，此题需要用多重背包，对每一件物品进行讨论，是用01背包还是完全背包，
用01 背包不优化有可能超时（看其他博主的博文），要用什么优化了？二进值优化。
此方法确实可以优化，但为什么可行了，不会答案错误吗？
个人理解：
对一个容量为7的物品来说：可二进制分为1 2 4；分成三个物品
（对一个容量为8的物品来说：可二进制分为1 2 4 1；分成四个物品）
按照动态规划的思路来说，用动态转移方程来决定选不选某个物品 ，在各种选与不选的组合中，正好考虑了是否选 容量为 1，2，3，4，5，6，7的物品 ，因为 在 容量为1 2 4 的物品中选出一些来 ，可以组成 容量为 1 ，2 ，3 ，4 ，5 ，6，7的物品
大佬的严格证明：https://blog.csdn.net/dextrad_ihacker/article/details/50923210
最后统计有多少的 dp[i]>=0 ,
为什么了，首先 i-weight==0时，此时的 i 是能凑出来的，dp[i]=0了，
对于 i-weight== j 若dp[j]>=0,说明 j 是能 凑出来的 ，则 i = j+weight 此时的 i 能凑出来的，动态转移方程为dp[i]=max(d[i],dp[i-weight]+value) , dp[i]>=0 这样就把 i 这个状态标记了
所以 对于所有的dp[i]>=0 ， 此时的 i 都能凑出来
#include <iOStream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int dp[1000010]; //dp[i] 该阶段下容量为i时的最优解
int bag;
void ZeroOnePack(int weight,int value)
{
int i;
for(i=bag;i>=weight;i--)
{
dp[i]=max(dp[i],dp[i-weight]+value);
}
}
void CompletePack(int weight,int value)
{
int i;
for(i=weight;i<=bag;i++)
{
dp[i]=max(dp[i],dp[i-weight]+value);
}
}
void Multiple(int weight,int value,int number)
{
if(bag<=number*weight)
{
CompletePack(weight,value);
return ;
}
else
{
int k=1;
while(k<=number)
{
ZeroOnePack(k*weight,k*value);
number=number-k;
k=k*2;
}
ZeroOnePack(number*weight,number*value);
}
}
void init()
{
int i;
dp[0]=0;
for(i=1;i<=bag;i++)
dp[i]=-INF;
}
int main()
{
int m,n;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,counts=0;
int value[150],number[150];
bag=m;
init();
if(m==0&&n==0)
break;
for(i=0;i<n;i++)
{
scanf("%d",&value[i]);
}
for(i=0;i<n;i++)
{
scanf("%d",&number[i]);
}
for(i=0;i<n;i++)
{
Multiple( value[i], value[i], number[i]);
}
for(i=1;i<=m;i++)
{
if(dp[i]>=0)
counts++;
}
printf("%d\n",counts);
}
return 0;
}