洛谷 P1164

https://www.luogu.org/problemnew/show/P1164

題目背景

uim

神犇拿到了

uoi

的

ra

（鐳牌）後，立刻拉着基友

小A

到了一家……餐館，很低端的那種。

uim

指着牆上的價目表（太低級了沒有菜單），說：“随便點”。

題目描述

不過

uim

由于買了一些

輔（e）輔（ro）書

，口袋裡隻剩M元(M≤10000)。

餐館雖低端，但是菜品種類不少，有N種(N≤100)，第i種賣ai元(ai≤1000)。由于是很低端的餐館，是以每種菜隻有一份。

小A

奉行“不把錢吃光不罷休”，是以他點單一定剛好吧

uim

身上所有錢花完。他想知道有多少種點菜方法。

由于

小A

肚子太餓，是以最多隻能等待1秒。

輸入輸出格式

輸入格式：

第一行是兩個數字，表示N和M。

第二行起N個正數ai（可以有相同的數字，每個數字均在1000以内）。

輸出格式：

一個正整數，表示點菜方案數，保證答案的範圍在int之内。

輸入輸出樣例

輸入樣例#1： 複制

4 4
1 1 2 2
           

輸出樣例#1： 複制

3
           

思路：動态規劃，f[i]表示花掉i元的點菜方法數，a[i]表示第i個菜品的價格，假設你有j元，那麼對于第i個菜品，你可以選也可以不選，根據加法原理有：f[j]=f[j]+f[j-a[i]]。這就是轉移方程。

#include<iostream>
using namespace std;

int f[10005];

int main()
{
    int n,m;
    cin>>n>>m;  //0 1背包 每個菜選或不選 選的話錢減少 不選錢不變 計算方案數加法原理
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    f[0]=1; //如果目前錢數剛好等于菜的價錢
    for(int i=0;i<n;i++)
        for(int j=m;j>=a[i];j--)
            f[j]=f[j]+f[j-a[i]];
    cout<<f[m]<<endl;
    return 0;
}
           

另解：這道題資料比較弱，搜尋+剪枝也可以過掉。

#include<iostream>
#include<algorithm>
using namespace std;

int m,n;
int a[105];
int cnt=0;

void dfs(int sum,int i);

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    dfs(0,0);
    cout<<cnt<<endl;
    return 0;
}

void dfs(int sum,int i)
{
    if(sum==m)
    {
        cnt++;
        return ;
    }
    else if(sum>m||i>=n)
        return ;
    dfs(sum+a[i],i+1);
    dfs(sum,i+1);
}