给定一个信封，最多只允许贴N(N<=100)张邮票，现在我们有m(m<=100)中邮票，面值分别为：x1，x2,......，xm分，(xi<=255,为正整数），并假设各种邮票都有足够多张。
要求计算所能获得邮资的最大范围。即求最大值MAX，使在1－－－MAX之间的每一种邮资都能得到。
例如：N＝4，有2中邮票，面值分别为1分，4分，于是可以得到1－10分和12分，13分，16分邮资，由于得不到11和15分，所以MAX＝10；
输入格式：
从文本stamp.in中读入数据，第一行为最多粘贴的邮票数N；第二行为邮票种数m；以后m行个有一个数字，表示邮票的面值xi。
输出格式：
1)若最大值为空，则在屏幕上输出MAX＝0；
2）若最范围不为空，则把结果输出到屏幕上。
例如：
输入
4
2
1
4
输出：
MAX＝10；
测试数据：
10
5
2
4
6
8
10
结果：MAX＝0；
邮票问题~不要求代码 ~给算法的思想就行

貌似有状态转移方程……

f[i]=max{f[i-w[j]]}
w[j]为所有邮票面额

我原来也是这样想的 但是 好像不行

GCC下编译通过

#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
    int size,num;
    int val[100],cnt[25501];
    memset(cnt,0,sizeof(cnt));
    cin>>size>>num;
    for(int i=0;i<num;i++) cin>>val[i];
    int s = 0;
    do{
        s ++;
        for(int i=0;i<num;i++){
            if(s-val[i]<0) continue;
            if(cnt[s]==0||cnt[s]>cnt[s-val[i]]){
                cnt[s] = cnt[s-val[i]] + 1;
            }
        }
    }while(cnt[s]!=0&&cnt[s]<=size);
    cout<<s-1<<endl;
}

其中cnt[s] 表示总面值为s最少需要多少张邮票

[[it] 本帖最后由 Eastsun 于 2008-10-26 19:42 编辑 [/it]]

这种题裸搜肯定要超，所以用动规的思路。

谢谢