题目描述：
给出N个盒子（N<=100），每个盒子有一定数量的糖果（每个盒子的糖果数<=100）,现在有q次查询，每次查询给出两个数k，m，问的是，如果从N个盒子中最多打开k个盒子（意思是打开1~k个盒子）能否使得糖果的总数恰好等于m，如果可以则输出Yes，否则输出No
题目分析：
对于普通的0-1背包我们经过优化之后用一个一维数组dp[j]表示的是前i个物品，容量为j时的可以获得的最大的价值，但是本题有些不同的是，我们求的dp[j]表示的是前i个盒子，容量恰好为j时，可以选择打开的盒子的最少个数（此处有一个不同之处在于，对于普通的0-1背包容量为j时的最大值可以是没有放满j的容量的，但是本题题意要求的是恰好放满m的容量，所以在推理动态转移方程的时候，如果dp[j-w[i]]的种数为0，则恰好为j就是不可能的）
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std; int dp[];
int w[]; int main(){
int cnt = ;
int n, q;
while(scanf("%d%d", &n, &q) != EOF){
printf("Case #%d:\n", cnt++);
int sum = ;
for(int i = ; i <= n; i++){
scanf("%d", &w[i]);
sum += w[i];
}
memset(dp, , sizeof(dp));
dp[w[]] = ; //对于第一个盒子而言，只有dp[w[1]] = 1这一种情况
for(int i = ; i <= n; i++){ //从第二个盒子开始遍历
for(int j = sum; j >= w[i]; j--){
if(dp[j] == ){ //如果当前为0且前驱状态不为0，则构成当前容量可以打开的最少的盒子数自然是前一种的最少数+1
if(dp[j-w[i]] != ){
dp[j] = dp[j-w[i]] + ;
}
}else{ //如果当前状态不是0且前驱的状态也不为0 则取前驱+1，和当前状态的最小值
if(dp[j-w[i]] != ){
dp[j] = min(dp[j], dp[j-w[i]] + );
}
}
}
dp[w[i]] = ; //每次dp[w[i]]都是为1 这里需要补上，因为上述的动态转移方程当j==w[i]时是不处理的
}
int k, m;
for(int i = ; i <= q; i++){
scanf("%d%d", &k, &m);
if(dp[m] <= k && dp[m] != ) printf("Yes\n");
else printf("No\n");
}
}
return ;
}