这个想法不错，但是在将超出的钱与所有数目的价格相减的过程中要添加一个条件，就是超出的价格A与所有书目价格对比（从大到小），遇到第一个不大于A的数目时，做出判断，如果去掉这本书以后，得到新的超出的价格A1与剩下的书价相比是否有小于或者等于A1的，若有，则这本书可以退掉，若没有，则不能退掉（这个条件必须有，也就是说我有可能退掉两本或者三本价格更小的书比只退一本价格高的书更适合）。

比如五本书价格分别为9、8、5、5、3,工资设为20，理论上最合适的组合是9、8、3；算法过程：1、sum=30；2、差价A1=30-20=10；3、10与五本书价格相比，第一个9比它小，如果去除的话，差价A2=1，但是找不到比1小的数目了，不能去掉，接下来改为去掉8，差价A2=2，还是不行，改为去掉5，可以那么去掉5这本书，剩下的9、8、5、3递归知道差价小于等于零结束。

一道 DP 题

ans[i] 表示 工资为 i 时，最多花的钱

#include <stdio.h>

#define MAX 2000

int main(int argc, char *argv[])
{
    int S, n, p[MAX], ans[MAX];

    while (scanf("%d", &S) != EOF)
    {
        scanf("%d", &n);
        for (size_t i = 0; i < n; i++)  scanf("%d", &p[i]);
        for (size_t s = 0; s <= S; s++)  ans[s] = 0;
        for (size_t i = 0; i < n; i++)
        for (size_t s = S; s >= p[i]; s--)
        {
            if (ans[s] + p[i] <= s)  ans[s] += p[i];
            else if (ans[s] < p[i] + ans[s - p[i]])
                ans[s] = p[i] + ans[s - p[i]];
        }
        printf("%d\n", ans[S]);
    }
    return 0;
}

版主这个方法不错。
R:\>a
10
3
2
3
4
Ans: 0,0,0,0,0,0,0,0,0,0,2,
Ans: 0,0,0,0,0,0,0,0,0,2,2,
Ans: 0,0,0,0,0,0,0,0,2,2,2,
Ans: 0,0,0,0,0,0,0,2,2,2,2,
Ans: 0,0,0,0,0,0,2,2,2,2,2,
Ans: 0,0,0,0,0,2,2,2,2,2,2,
Ans: 0,0,0,0,2,2,2,2,2,2,2,
Ans: 0,0,0,2,2,2,2,2,2,2,2,
Ans: 0,0,2,2,2,2,2,2,2,2,2,
Ans: 0,0,2,2,2,2,2,2,2,2,5,
Ans: 0,0,2,2,2,2,2,2,2,5,5,
Ans: 0,0,2,2,2,2,2,2,5,5,5,
Ans: 0,0,2,2,2,2,2,5,5,5,5,
Ans: 0,0,2,2,2,2,5,5,5,5,5,
Ans: 0,0,2,2,2,5,5,5,5,5,5,
Ans: 0,0,2,2,3,5,5,5,5,5,5,
Ans: 0,0,2,3,3,5,5,5,5,5,5,
Ans: 0,0,2,3,3,5,5,5,5,5,9,
Ans: 0,0,2,3,3,5,5,5,5,9,9,
Ans: 0,0,2,3,3,5,5,5,7,9,9,
Ans: 0,0,2,3,3,5,5,7,7,9,9,
Ans: 0,0,2,3,3,5,6,7,7,9,9,
Ans: 0,0,2,3,3,5,6,7,7,9,9,
Ans: 0,0,2,3,4,5,6,7,7,9,9,
9

版主这个是自己想出来的吗,还是经验?虽然只有几行,试数的时候花了不少时间

我哪里想得出来。。。

只是觉得和背包问题很相似，就那样建模了。