买东西

NC215081. 买东西

描述

小明和小红来到了一家商店，这家商店有n个商品，每个商品都有个价格，但是小明只有k元。这时小红有个问题，在这n个商品中，每个商品都有买和不买两种情况，也就是说有 $2 ^ n$ 种购买方案，问在这些方案中小明因身上的钱不够无法购买的有多少种？

输入描述

一行两个整数，n   k，分别表示n个商品，小明身上的金额k元。

第二行n个整数，表示每个商品的价格（元）。

输出描述

表示无法购买的方案数。

示例1

输入:

3 8
1 4 6

输出:

说明:

[1, 4, 6] 和 [4, 6]这两种方案价格都大于8所以无法购买的有2种。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 286ms, 内存消耗: 392K, 提交时间: 2020-12-18 22:41:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,ans,a[207];

void dfs(int p,ll SUM) 
{
	if(SUM>k) return;
	if(p==n+1)
	{
		ans++;
		return;
	}
	dfs(p+1,SUM+a[p]);
	dfs(p+1,SUM);
}

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dfs(1,0);
	ll sum=pow(2,n)-ans;
	cout<<sum;
}

上一题

下一题

详情