背包問題 洛谷P1164 小A點菜

題目連結：

https://www.luogu.org/problem/P1164

參考代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;//菜的種類和口袋裡的錢,種類數
int a[110],f[110][110]={0};
void dfs(int x,int m)
{
	if(m==0) { ans++;return;}
	if(x<1)return;//走完了
	dfs(x-1,m);//不選
	if(m>=a[x])  dfs(x-1,m-a[x]);//選
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(n,m);
	cout<<ans;
	return 0;
}
           

——————————————————————————

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110],f[110];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		f[0]=1;
		//目前第i種物品恰好為j元錢，是以可以隻買它自己。這種情況其實包含在1中，但是由于f[i][0]=0，
		//是以不會算入這種情況。是以我們要把所有的f[i][0]更新成1，
		for(int j=m;j>=a[i];j--)
			f[j]+=f[j-a[i]];//累加方案,現在的花費+=我不點這個菜的時候的花費
	}
	cout<<f[m];
	return 0;
}
           

（1）if(j==第i道菜的價格)f[i][j]=f[i-1][j]+1;

（2）if(j>第i道菜的價格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的價格];

（3）if(j<第i道菜的價格) f[i][j]=f[i-1][j];

參考代碼：

#include<bits/stdc++.h>
using namespace std;
int a[101],f[101][10001]={0};
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)
      for(int j=1;j<=m;++j)
      {
          if(j==a[i])f[i][j]=f[i-1][j]+1;
          if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
          if(j<a[i]) f[i][j]=f[i-1][j];
      }
    cout<<f[n][m];
    return 0;
}