首页 > 试题广场 >

选择物品

[编程题]选择物品

热度指数：3961 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有 $n$ 个物品可供选择，必须选择其中 $m$ 个物品，请按字典序顺序输出所有选取方案的物品编号

$1 2 3$ 与 $312$ 与 $321$ 等被认为是同一种方案，输出字典序最小的 $123$ 即可

数据范围： $1\le m\le n \le 10\$

进阶：时间复杂度 $O(n!)\$ ，空见复杂度 $O(n)\$

输入描述:

对于每一组测试数据，每行输入 $2$ 个数 $n$ 和 $m$ 。

$1 \le m \le n \le 10$

输出描述:

对于每组输入样例，按字典序输出所有方案选择物品的编号，每种方案占一行

示例1

输入

4 1

输出

示例2

输入

5 2

输出

算法知识视频讲解

pein531

计算全体组合数，DFS的模板题

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    public static ArrayList<Stack<Integer>> res = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        dfs(n, m, 1, new Stack<Integer>());
        for(Stack<Integer> stack: res){
            for(Integer elem : stack)
                System.out.print(elem + " ");
            System.out.println();
        }
    }
    
    private static void dfs(int n, int m, int depth, Stack<Integer> stack) {
        if(stack.size() == m){
            res.add((Stack<Integer>)stack.clone());
            return;
        }
        for(int i = depth; i <= n; i++){
            stack.push(i);
            dfs(n, m, i + 1, stack);
            stack.pop();
        }
    }
}

再来个scala版本的，由于栈是先进后出，因此在将栈变为数组的时候需要进行反转才能保持原先栈底到栈顶的顺序

import scala.io.StdIn
import scala.collection.mutable._

object Main {
    def main(args: Array[String]): Unit = {
        val params: Array[String] = StdIn.readLine().split(" ")
        val n = params(0).toInt
        val m = params(1).toInt
        val res = ListBuffer[Array[Int]]()
        dfs(1, n, m, Stack[Int](), res)
        res.foreach((row: Array[Int]) => println(row.mkString(" ")))
    }
    
    def dfs(depth: Int, n: Int, m: Int, combination: Stack[Int], res: ListBuffer[Array[Int]]): Unit = {
        if(combination.size == m){
            res.append(combination.toArray.reverse);
            return
        }
        for(i <- depth to n){
            combination.push(i)
            dfs(i + 1, n, m, combination, res)
            combination.pop
        }
    }
}

编辑于 2021-08-16 22:52:40 回复(0)

爆爆只是想帮忙

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

vector<int> path;
void backtracking(int n, int m, int startIndex){
    if(path.size() == m){
        for(int i = 0; i < m; i++){
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i = startIndex; i <= n; i++){
        if(n - i + 1 < m - path.size()) break;//剪枝
        path.push_back(i);
        backtracking(n, m, i + 1);
        path.pop_back();
    }
}

int main(){
    int n, m;
    while(cin >> n >> m){
        backtracking(n, m, 1);
    }
}

发表于 2022-03-12 18:47:51 回复(0)

大虾飞哥哥

m, n =map(int, input().split())

cur =[]

res =[]

defdfs(index):

iflen(cur) ==n:

#res.append(cur[:])

print(" ".join(map(str, cur)))

return

iflen(cur) > n:

return

fori inrange(index, m+1):

cur.append(i)

dfs(i+1)

cur.pop()

dfs(1)

发表于 2022-02-28 17:03:18 回复(0)

墨羽魂韶

正常dfs模板题
但是介于本人不会, 所以选择了暴力一点的方式

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();


        for(int a = 1; a <= n; ++ a) {
            if(m > 1) for(int b = a + 1; b <= n; ++ b )
                if(m > 2) for(int c = b + 1; c <= n; ++ c)
                    if(m > 3) for(int d = c + 1; d <= n; ++ d)
                        if(m > 4) for(int e = d + 1; e <= n; ++ e)
                            if(m > 5) for(int f = e + 1; f <= n; ++ f)
                                if(m > 6) for(int h = f + 1; h <= n; ++ h)
                                    if(m > 7) for(int i = h + 1; i <= n; ++ i)
                                        if(m > 8) for(int j = i + 1; j <= n; ++ j)
                                            if(m > 9) for(int k = j + 1; k <= n; ++ k)
                                                if(m > 10) for(int l = k + 1; l <= n; ++ l)
                                                    if(m > 11) for(int o = l + 1; o <= n; ++ o)
                                                        System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k+" "+l+" "+o);
                                                    else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k+" "+l);
                                                else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k);
                                            else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j);
                                        else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i);
                                    else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h);
                                else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f);
                            else System.out.println(a+" "+b+" "+c+" "+d+" "+e);
                        else System.out.println(a+" "+b+" "+c+" "+d);
                    else System.out.println(a+" "+b+" "+c);
                else System.out.println(a+" "+b);
            else System.out.println(a);

        }
    }
}

#include <iostream>
#include <vector>
using namespace std;
#define int long long
vector<int> ans;
int m, n;

void dfs(int l) {
//    if(l > n) return;
    if(ans.size() == m) {
        for(int a : ans) cout << a << " ";
        cout << endl;
    }

    for(int i = l; i <= n; ++ i) {
        ans.push_back(i);
        dfs(i+1);
        ans.pop_back();
    }
}
signed main() {
    cin >> n >> m;
    dfs(1);
}

编辑于 2022-03-13 12:37:39 回复(0)

黄_昏

非递归实现，空间复杂度O(m)：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] stack = new int[m];
        int i;
        for (i = 0; i < m; i++) {
            stack[i] = i + 1;
        }
        int bot = stack[0];
        while (bot + m <= n) {
            for (i = 0; i < m; i++) {
                System.out.print(stack[i] + " ");
            }
            System.out.println();

            for (i = m - 1; i >= 0; i--) {
                if (stack[i] + 1 <= n && m - 1 - i + stack[i] + 1 < n + 1) {
                    stack[i] += 1;
                    break;
                }
            }
            i++;
            for (; i < m ; i++) {
                stack[i] = stack[i - 1] + 1;
            }
            bot = stack[0];
        }
        for (i = 0; i < m; i++) {
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
}

发表于 2023-03-26 18:25:52 回复(0)

粉色少女姜承録

//说实话，不太明白为啥不对，有大佬能解答一下吗
import java.util.Random;

public class DOM {

    static Random a1 = new Random();
//    static int m = a1.nextInt(20)+1;
//    static int n = a1.nextInt(m)+1;
    static int m=10;
    static int n=3;
    static int[]a=new int[m];
    static  int[] b = new int[n];

    public static void C(int m,int n){
        for(int i=n;i<=m;i++) {
            b[n-1] = i-1;
            if(n>1)
                C(i-1,n-1);
            else {
                for(int j=0;j<DOM.n;j++){
                    System.out.print(a[b[j]] + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

    public static void main(String[] args){
        System.out.println(m);
        System.out.println(n);

            for (int i = 0; i <m ; i++) {
                a[i]=i+1;
            }
        C(m,n);
    }
}

发表于 2022-08-20 15:25:54 回复(0)

Python

zhq1999

track = []
def trackback(i,targetnum):
    if len(track) == target_num:
        for i in range(len(track)):
            print(track[i],end =" ")
        print()
    for k in range(i,len(data)):
        track.append(data[k])
        trackback(k+1, targetnum)
        track.pop()

if __name__ == "__main__":
    num = list(map(int,input().split()))
    target_num = num[1]
    data = []
    for i in range(num[0]):
        data.append(i+1)    
    trackback(0,target_num)

发表于 2022-08-03 17:15:54 回复(0)

incubus918

#include <iostream>
using namespace std;
int a[15];
bool st[15];
int n,m;
void dfs(int x,int t){
    if(t == x + 1){
        for(int j = 1;j <= x;j++)cout<<a[j]<<" ";
        cout<<endl;
        return;
    }
    for(int i = 1;i <= n;i++){
        if(!st[i] && i > a[t-1]){
            st[i] = true;
            a[t++] = i;
            dfs(x,t);
            t--;
			st[i] = false;    
        }
    }
}
int main(){
    cin>>n>>m;
    dfs(m,1);
    
    return 0;
}

简单的dfs

发表于 2022-04-06 22:42:18 回复(0)

牛客144721421号

进阶做法：DFS+回溯法

时间复杂度：O(n!)，空间复杂度：O(m)

#include <iostream>
#include <vector>
using namespace std;

void dfs(int n, int m, int i, int j, vector<vector<int>>& ans, vector<int>& temp){
    if(j == m){//j记录在temp中已有几个数，满了就插入答案数组
        ans.push_back(temp);
        return;
    }
    for(int k = i; k <= n; k++){
        temp.push_back(k);
        dfs(n, m, k + 1, j + 1, ans, temp);//选择的下一个数从k+1开始，避免重复
        temp.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n, m;
    vector<vector<int>> ans;//ans存储全部方案
    vector<int> temp;//temp临时存储一种方案
    cin >> n >> m;
    dfs(n, m, 1, 0, ans, temp);
    for(size_t i = 0; i < ans.size(); i++){
        for(size_t j = 0; j < ans[0].size(); j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

发表于 2022-04-06 16:02:47 回复(0)

牛客457782079号

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] str=br.readLine().trim().split(" ");;
        int n=Integer.parseInt(str[0]);
        int m=Integer.parseInt(str[1]);
        List<Integer> list=new ArrayList<>();
        getAns(list,0,0,n,m);






    }
    public static void getAns(List<Integer> list,int index,int count,int n,int m){
        if(count==m){
            for(int i=0;i<list.size()-1;i++){
                System.out.print(list.get(i)+" ");
            }
            System.out.println(list.get(list.size()-1));
            return;
        }
        if(index==n)return;
        if(m-count>n-index)return;
        list.add(index+1);
        getAns(list,index+1,count+1,n,m);
        list.remove(list.size()-1);
        getAns(list,index+1,count,n,m);


    }
}

发表于 2022-03-31 14:45:06 回复(0)

十年如此回忆

line = input().split()
n, m = int(line[0]), int(line[1])
 
def dfs(state, cur):
    if len(cur)==m:
        print(' '.join(cur))
        return
    for i in range(1, n+1):
        cur_state = 1<<(i-1)
        if cur_state&state&nbs***bsp;(cur and i<int(cur[-1])):
            continue
        dfs(state|cur_state, cur+[str(i)])
         
 
dfs(0, [])

dfs+状态压缩

发表于 2022-03-24 20:47:25 回复(0)

啥啊啥啊

答案必须按照DFS的顺序输出，不然即使答案对顺序不对也算错。哪个人才写的答案比对

发表于 2022-03-24 09:23:44 回复(0)

Kaitokuroba7

def func(nums):
    track = []
    n = len(nums)
 
    def backtrack(index=0):
        if len(track) == target_num:
            for x in track:
                print(x, end=" ")
            print()
 
        for i in range(index, n):
            track.append(nums[i])
            backtrack(i + 1)
            track.pop()
 
    backtrack()
 
 
row_one = list(map(int, input().split()))
 
nums = [i + 1 for i in range(row_one[0])]
target_num = row_one[1]
 
func(nums)

发表于 2022-03-21 15:54:17 回复(0)

牛客329914863号

加一个自己的，也是用的栈来dfs：

package meituantest;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Test2 {
    static Stack<Integer> stack;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        stack=new Stack<Integer>();
        digui(m, n);
        sc.close();

    }
    public static void digui(int m,int n) {
        if(stack.size()==m) {
            for(Integer i:stack) {
                System.out.print(i+" ");
            }
            System.out.println();
            stack.pop();
        }else {
            int size=stack.size();
            for(int i=size==0?1:stack.peek()+1;i<=n;i++) {
                stack.push(i);
                digui(m,n);
            }
            if(size>0) {
                stack.pop();
            }
        }
    }
}

发表于 2022-03-10 21:43:25 回复(0)

Delicacies

注意Python递归是引用，需要解除引用，防止下一层调用对上一层保存值的修改。

def dfs(curr, start, n, k):
    if len(curr) == k:
        # 由于ret里面存的是curr的引用，下一层递归对curr的修改会影响ret里面的结果，
        # 所以要把curr里面的值拷贝出来,用copy()
        ret.append(curr.copy())  # 注意解除引用
        return
    for i in range(start, n+1):
        dfs(curr+[i], i+1, n, k)
    return

n,k = map(int, input().split())
curr = []
ret = []
dfs(curr,1,n,k)
for i in ret:
    for j in i:
        print(j,end=' ')
    print()

发表于 2022-03-09 12:25:21 回复(0)

随风起浪里个浪

#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int>&temp, int n, int m, int index){
    if (temp.size() == m){
        //输出temp
        for (int i = 0; i < temp.size(); i++){
            if (i == 0)
                cout << temp[i];
            else
                cout << " " << temp[i];
        }
        cout << endl;
        return;
    }
    else{
        for (int i = index; i <= n; i++){
            temp.push_back(i);
            dfs(temp, n, m, i + 1);
            temp.pop_back();
        }
    }
}
int main(){
    int n, m;
    while (cin >> n >> m){
        vector<int> temp;
        dfs(temp,n,m,1);
    }
    return 0;
}

发表于 2022-03-03 12:39:20 回复(0)

Java

中二病也要写代码

终于有一道我能做的题了，，，

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
public class Main {
    public static ArrayList> res = new ArrayList();
    public static ArrayList path = new ArrayList();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        dfs(n, m, 1);
        for(ArrayList items: res){
            for(Integer elem : items){
                System.out.print(elem + " ");
            }
            System.out.println();
        }
    }
    private static void dfs(int n, int m, int index) {
        if(path.size() == m){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = index; i <= n; i++){
            path.add(i);
            dfs(n, m, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

发表于 2022-03-02 10:32:31 回复(0)

阳素凡

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    static List<int[]> list = new ArrayList<>();
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        dfs(0, n, m, new int[m]);
        for (int[] arr : list) {
            for(int i=0; i<m; i++){
                System.out.print(arr[i]);
                if(i < m-1){
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
 
    public static void dfs(int index, int n, int m, int[] arr){
        if(index==m){
            int[] tmp = Arrays.copyOf(arr, m);
            list.add(tmp);
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (index-1>=0 && arr[index-1]>=i){
                continue;
            }
            arr[index] = i;
            dfs(index+1, n, m, arr);
            arr[index] = 0;
        }
    }
}

发表于 2022-02-28 17:11:21 回复(0)

C/C++

AlbatrossLy

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& ans, vector<int>& tmp, int& n, int m, int pos)
{
    if(m == 0)
    {
        ans.push_back(tmp);
        return;
    }
    else
    {
        for(int i = pos; i <= n; i++)
        {
            tmp.push_back(i);
            dfs(ans, tmp, n, m - 1, i + 1);
            tmp.pop_back();
        }
    }
}


int main()
{
    int n, m;
    while(cin >> n >> m)
    {
        vector<vector<int>> ans;
        vector<int> tmp;
        dfs(ans, tmp, n, m, 1);
        for(const auto& e : ans)
        {
            for(const auto& q : e)
            {
                cout << q << " ";
            }
            cout << endl;
        }
    }
    
    return 0;
}

发表于 2022-02-10 18:51:10 回复(0)

牛客303091741号

由于n比较小，可以使用位操作找出1--pow(2, n)中所有含有m个1的数；for循环从大到小遍历，当检测当前数有m个1时，第n - x + 1位为1时输出x即可。

#include<iostream>
using namespace std;

bool count_ones(int& num, int& m) {
    int tmp = num;
    int ret = 0;
    for (; tmp != 0;) {
        if (tmp % 2) ret++;
        tmp = tmp >> 1;
    }
    if (ret == m) return true;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = (1 << n); i >= 1; i--) {
        if (count_ones(i, m)) {
            int cnt = 0;
            for (int p = 1; p <= n; p++) {
                if (i & (1 << (n - p))){
                    cnt++;
                    if(cnt == m) cout << p << endl;
                    else cout << p << ' ';
                }
            }
        }
    }
    return 0;
}

编辑于 2021-09-20 16:42:22 回复(0)