题目描述

由于uim买了一些辅导书，口袋里只剩M元(M≤10000)。

餐馆虽低端，但是菜品种类不少，有N种(N≤100)，第i种卖a_i 元(a_i≤1000)。

由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。

他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待1秒。

输入格式

第一行是两个数字，表示N和M。

第二行起N个正数a_i ​ （可以有相同的数字，每个数字均在1000以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在int之内

输入样例

4 4
1 1 2 2

输出样例

3

解法

思路

本题与一般的背包问题差别较大：

  1. 背包问题中f[]代表的是最终的要求的内容，本题是求点菜方法，所以f[]是点菜方法的集合。
  2. 总钱数是容量，每盘菜都有对应的价格，但是没有对应的价值，本题也不求价值。
  3. 本题的要求的东西，并不是物品的属性，所以并没有在输入时体现出来，即并不是固定的。
  4. 当j与w[i]相等时，需要单独处理，因为数组第一行都是0，而不是加1。加1是因为多了一种只买第i盘菜这种情况。
  5. 本题要求容量要耗尽，而不是普通的装最大价值。

不变的一点是二维数组仍然是横轴为种类，纵轴为容量：

  1. j>w[i]，f[i][j]=f[i-1][j]+f[i-1][j-w[i]]
  2. j=w[i]，f[i][j]=f[i-1][j]+1
  3. j<w[i]，f[i][j]=f[i-1][j]

代码

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,n=0;
    int f[101][10001]={},w[101]={};
    
    cin>>n>>t;
    
    for(int i=1;i<=n;i++){
            cin>>w[i];
            }
    
    for(int i=1;i<=n;i++){
            for(int j=1;j<=t;j++){
                    if(j<w[i]){
                               f[i][j]=f[i-1][j];
                               }
                    else if(j==w[i]){
                         f[i][j]=f[i-1][j]+1;
                         }
                    else
                         f[i][j]=f[i-1][j]+f[i-1][j-w[i]];
                    }
            }
    cout<<f[n][t];
    return 0;
    }