文章

10

粉丝

224

获赞

12

访问

50.6k

头像
回溯法
P1462 北京理工大学机试题
发布于2022年5月31日 09:34
阅读数 4.3k

 思路:对于每张邮票,要么选,要么不选。如果选,需要判断数量是否>0。如果不选,直接跳过本层向下一层搜索。使用set去重。

#include <bits/stdc++.h>
using namespace std;

int nums[3] = {5, 4, 6};
int val[3] = {8, 10, 18};

unordered_set<int> st;

int sum = 0;

void dfs(int beginIndex)
{
    if (beginIndex >= 3)
        return;
    if (sum > 0)
        st.insert(sum);
    for (int i = beginIndex; i < 3; i++)
    {
        if (nums[i] > 0)
        {
            nums[i]--;
            sum += val[i];
            dfs(i);
            sum -= val[i];
            nums[i]++;
        }
        dfs(i + 1);
    }
}

int main()
{
    dfs(0);
    printf("%d", st.size());
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发