HDU 1203 I NEED A OFFER!

http://acm.hdu.edu.cn/showproblem.php?pid=1203

依旧是0/1背包的问题. 水题，秒杀之。。O(∩_∩)O哈哈~

View Code

 1 #include <stdio.h>
 2 #define maxn 10005
 3 double ans[maxn], w[maxn];
 4 int v[maxn];
 5 int main()
 6 {
 7     int n, m, i, j;
 8     while(~scanf("%d%d",&m,&n),n||m)
 9     {
10         for(i = 0; i < n; i++)
11         scanf("%d%lf",&v[i],&w[i]);
12         for(i = 0; i <= m; i++) ans[i] = 0;
13         for(i = 0; i < n; i++)
14         for(j = m; j >= v[i]; j--)
15         if(ans[j-v[i]]+w[i]-(ans[j-v[i]]*w[i]) > ans[j])
16         ans[j] = ans[j-v[i]]+w[i]-(ans[j-v[i]]*w[i]);
17         printf("%.1lf%%\n",ans[m]*100);
18     }
19     return 0;
20 }