动态规划 专题

洛谷 P1164 小A点菜

题目背景

题目描述

输入输出格式

时空限制

  • 时间：1000ms
  • 空间：128MB

思路

法一：背包问题的动态规划

递推公式

1. 钱刚刚好，吃这道菜，即放入背包：dp[i][j] = dp[i-1][j]+1;
2. 钱多于这道菜，吃这道菜 + 不吃这道菜的方法数之和：dp[i][j] = dp[i-1][j] + dp[i-1][j-price[i]];
3. 钱不够，不吃这道菜，即不放入背包：dp[i][j] = dp[i-1][j];
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <math.h>
using namespace std;
int price[30001];
int dp[5000][5000];
int n,m;
int sum = 0;
int flag[1000];


int main(){
	cin >> n >> m;  //n是菜种类数，m是钱
	for(int i = 1; i <= n; ++i){
		cin >> price[i];
	}
	//memset(dp,0,sizeof(dp));
	//int count = 1; 
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){  //j从1递增到总钱数m
			if(j == price[i]){  //钱刚刚好，吃这个菜 
				dp[i][j] = dp[i-1][j]+1;  
			}
			else if(j > price[i]){  //钱多于这个菜，吃这个菜+不吃这个菜方法数之和 
				dp[i][j] = dp[i-1][j] + dp[i-1][j-price[i]];
			}
			else{  //钱不够，不吃这个菜 
				dp[i][j] = dp[i-1][j];
			}
		} 
	}
	cout << dp[n][m] << endl;
	return 0;
}
法二：DFS 深度优先搜索

因为菜至多只有 100 种，自然想到用搜索，进行剪枝之和，发现并不会爆，顺利 AC 。

要用一个 flag 数组表示当前菜是否被选过，选过置为 1 。从（0，0）开始深搜。

代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <math.h>
using namespace std;
int price[30001];
int dp[5000][5000];
int n,m;
int sum = 0;
int flag[1000];

//DFS
void dfs(int k, int x){
	if(k > m){  //菜价格大于总钱数 
		return;
	}
	if(k == m){  //菜价格刚好等于总钱数 
		sum++;
		return;
	}
	for(int i = x+1; i <= n; ++i){  //从下一道菜开始选 
		if(flag[i] == 0){  //没选过这道菜 
			flag[i] = 1;
			dfs(k+price[i],i);  //价格+这道菜价格，选择第i道菜 
			flag[i] = 0;  //剪枝 
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		scanf("%d",&price[i]);
	}
	dfs(0,0);
	cout << sum << endl;
	return 0;
}