[C++知识库]中央财经大学2001年c语言编程真题

题目：小刚假期同妈妈一起去书店，他选中了n本书，每本书的单价为：p1,p2,p3...pn元（均为整数）。不巧的是，妈妈只带了s(为整数)元钱，不够买这n本书（即：s<p1+p2+p3+...+pn)。妈妈同意将这s元全部用来买书，也就是小刚要从n本书中选出m本，使得这m本的价格和刚好等于s，即p1+p2+p3+...+pn=s，请你编程序将所有满足这一条件的i1,i2,i3,...im依次打印出来。

分析：题目乍一看是动态规划的0-1背包问题，但题目要求输出所有条件而不是输出可能的排列数，所以我的知识不足以在动态规划的思路里面解出此题。另寻它法。题目中钱数、书数都是不定值，暴力破解不可取。最后在这篇帖子中找到思路并做了提炼和修改。

#include "stdio.h"
#include "stdlib.h"

#define NULL 0
int *books;

void print();

void Purchase();

void main(void) {
    int *prices;//数组：存储每本书的价格
    int i;
    int k = 0;//已确定购买的书的数量
    int count;//待购买书的数量
    int sum = 0;//待购买书的总价格
    int money;//你手里的钱
    printf("How much money in your packet?\nmoney=");
    scanf("%d", &money);
    printf("\n");
    printf("How many books do you want!\ncount=");
    scanf("%d", &count);
    printf("\n");
    books = calloc(count, sizeof(int));
    if (books == NULL) {
        fprintf(stderr, "Out of Memories!\n");
        exit(0);
    }
    prices = calloc(count, sizeof(int));
    if (prices == NULL) {
        fprintf(stderr, "Out of Memories!\n");
        exit(1);
    }
    printf("Please enter the unit price of the book\n");
    for (i = 0; i < count; i++) {
        printf("prices[%d]=", i + 1);
        scanf("%d", &prices[i]);
        printf("\n");
        sum += prices[i];
    }
    Purchase(prices, count, money, k, sum, prices);
    free(books);
    free(prices);
}

// outset参数用来标识当前所处理的书在清单中的编号
void Purchase(int *prices, int count, int money, int k, int sum, int *outset) {
    if (*prices == money) {
        books[k] = prices - outset;
        print(k);
        return;
    } else if ((sum >= money) && (*prices < money)) {
        books[k] = prices - outset;
        Purchase(prices + 1, count - 1, money - *prices, k + 1, sum - *prices, outset);
    }
    if ((sum >= money) && (*(prices + 1) <= money)) {
        Purchase(prices + 1, count - 1, money, k, sum - *prices, outset);
    }
}

void print(int k) {
    int i;
    for (i = 0; i <= k; i++)
        printf("%d \t", books[i] + 1);
    printf("\n");
}

算法欠缺：题目中对钱数和书的单价只做了整数的要求，没有做唯一性要求、增减性要求。所以该算法中对于出现书的价格相同、乱序的情况没做处理，如果增加排序和去重的算法，就会增加很多无聊代码。考虑到央财试卷的考试难度和要求，算了。