点菜

编程入门 行业动态 更新时间:2024-10-10 02:21:42

点菜

点菜

(很锻炼思想的一题)

题目描述

不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩MM元(M \le 10000)(M≤10000)。

餐馆虽低端,但是菜品种类不少,有NN种(N \le 100)(N≤100),第ii种卖a_iai​元(a_i \le 1000)(ai​≤1000)。由于是很低端的餐馆,所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”,所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。

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

输入输出格式

输入格式:

 

第一行是两个数字,表示NN和MM。

第二行起NN个正数a_iai​(可以有相同的数字,每个数字均在10001000以内)。

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制

4 4
1 1 2 2

输出样例#1: 复制

3
 


解析

我们先用dp做,我们发现想这种典型的背包问题,都是两种:放与不放(吃与不吃)的问题,我们arr数组储存每道菜的价格,w[i][j]表示前i个菜用完j元(为什么这里是用完呢,因为题目规定的是一定要用完这j元)的方案数,所以我们可以分为以下:

1.j>arr[i],也就是当前的菜价格小于j,那么w[i][j]=w[i-1][j]+w[i-1][j-arr[i]],w[i-1][j]表示我不吃arr[i]这道菜用完j元的方案数,w[i-1][j-arr[i]]表示我吃这道菜的方案数。我是这样理解的:(重点!!!

   显示w[i][j]可以分成两种,一种是一定要买arr[i]凑够j的方案数和不买而凑够的方案数

   w[i-1][j]就是在前i-1道菜里面选出可以凑够j元的方案数,也就是不买arr[i]凑够j元的方案数。

   w[i-1][j-arr[i]]表示在前i-1道菜里面选出凑够j-arr[i]元的方案数,因为前i-1道菜里面选出凑够j-arr[i]元的方案数其实就等于一定要买arr[i]才凑够j的方案数,我们可以想一下:1  1  2  2  我们w[4][4]中一定要买arr[4]的方案有:1 1 2和2  2这个的的方案数也就是w[3][2]的方案数:1  1和2,w[3][2]的每种方案加上arr[i]就是w[4][4]的方案

 

2.j==arr[i],w[i][j] = w[i - 1][j] + 1,这个一就是买arr[i]方案数,只有一种

 

3.j<arr[i],w[i][j] = w[i - 1][j] ,不能买arr[i]了

所以代码:

#include<iostream>
using namespace std;
int w[102][10002];
int arr[102];
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> arr[i];}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (j == arr[i])w[i][j] = w[i - 1][j] + 1;if (j > arr[i])w[i][j] = w[i - 1][j] + w[i - 1][j - arr[i]];if (j < arr[i])w[i][j] = w[i - 1][j];}}cout << w[n][m] << endl;system("pause");return 0;
}

接下来就是降维的方法,这是基于充分理解了前面的方法才能懂的

我们在采用二维数组的时候,是采用:

w[i][j] = w[i - 1][j] + w[i - 1][j - arr[i]]

那么我们需要理解一下等号后面的表示什么:

w[i - 1][j]:表示前i-1个物品放入v的最大价值,这里的j是从0~v循环的

w[i - 1][j - arr[i]]:表示前i-1个物品放入j-v[i]的最大价值

因为我们是用二维数组保存这两个状态,所以我们随时都可以取出这两个状态,但是我们现在用一维怎么去表示这两个状态呢?

 

一维数组中我们肯定也是先要循环i从1到n,循环所有物品,那么我们可以知道,当我们进行第i轮循环的时候,此时dp[]里面储存的正式前面i-1个物品的最大价值,所以可以确定第一层循环

 for(int i=1;i<=n;i++)

所以我们之前的两个状态就可以被替代:

w[i - 1][j]--->w[j]

w[i-1][j-arr[i]]--->w[j-arr[i]]

所以,由于我们循环会让w被不断替换掉,而且我们每一轮循环只需要知道上一轮的状态,所以我们顺理成章的去掉了第一维

然后我们发现,我们下面一层循环就是从arr[i]~m(当前物品大小~总容量),因为我们之前二维数组是会对前一轮的状态进行保存,也就是dp[i-1][j]和dp[i-1][j-arr[i]]。但是现在一维数组我们在当前第i层循环就会改变dp[i]数组,所以我们需要从后往前循环,这样才能保证w[j-arr[i]]是上一轮的状态。

降维代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110
using namespace std;
int n,m,a[N],f[10010];
int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);f[0]=1;for(int i=1;i<=n;i++)for(int j=m;j>=a[i];j--)f[j]=f[j]+f[j-a[i]];cout<<f[m];return 0;
}

递归做法:

注意mark的作用就是剪枝

//
#include<iostream>
using namespace std;
int sum = 0;
int n, m;
int pri[103];//价格数组
int res[103];//记录是否点过
int flag = 0;
void dfs(int sum, int mark)//sum表示当前所有点的菜的价格总和,mark表示当前的菜的序号
{if (sum > m)return;if (sum == m)//如果已经达到了m元{flag++;return;}for (int i = mark + 1; i <=n; i++)//i不用每次从1开始,因为mark前面的已经点过了{if (res[i] == 0){res[i] = 1;dfs(sum + pri[i], i);res[i] = 0;}}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> pri[i];}dfs(0, 0);cout << flag << endl;system("pause");return 0;
}

 

更多推荐

点菜

本文发布于:2024-02-24 20:41:39,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1696589.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!