#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int n;
float f[5005];

int main(int argc, const char *argv[])
{
scanf("%d", &n);
for (int i = 1; i <= n * 5; ++i)
f[i] = 100001;
int ans = 0;
for (int i = 1; i <= n; ++i)
{
float t;
int v;
scanf("%f %d", &t, &v);
for (int j = n * 5; j >= v; --j)
{
f[j] = min(f[j], f[j - v] + t);
if (f[j] <= 100.00000 && j > ans)
ans = j;
}
}
printf("%d\n", ans);
return 0;
}

float F[5001];除了F[0]其他初始化为INF.
费用和权值位置相反后还是01背包问题，核心代码：

for(i=1;i<=n;i++)
{
scanf("%f%d",&v,&w); sum+=w;
for(j=sum;j>=w;j--) F[j]=minf(F[j],F[j-w]+v);
//更新获得权值j所花的最少时间F[j]。(v是费用，w是权值)
}
最后扫一遍找答案。
顺便说个浮点数判断相等问题。

double a,b,c;//float精度太小,我电脑上用double才运行正确
a=100.0;
b=100.0+1e-5;//系统可判断正确
c=100.0+1e-6;//系统可判断错误
由于浮点数的误差，系统会判断a!=b,a==c.
如果遇到6位小数以上(包括6位)判断相等的情况，需要用<p>(a-b<1e-9 && a-b>-1e-9)<p>(1e-10……也可)。
然而本题忽略了这个问题也AC了。
所以我干脆也用float，6、7位精度也够了。
然后扫一遍找答案
for(i=1;i<=5000;i++)
//if(F[i]-100.0<1e-9 && F[i]-100.0>-1e-9 && i>=ans) ans=i; //double F[i]
if(F[i]<=100.0 && i>=ans) ans=i;
printf("%d",ans);

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int n;
float f[5005];

int main(int argc, const char *argv[])
{
scanf("%d", &n);
for (int i = 1; i <= n * 5; ++i)
f[i] = 100001;
int ans = 0;
for (int i = 1; i <= n; ++i)
{
float t;
int v;
scanf("%f %d", &t, &v);
for (int j = n * 5; j >= v; --j)
{
f[j] = min(f[j], f[j - v] + t);
if (f[j] <= 100.00000 && j > ans)
ans = j;
}
}
printf("%d\n", ans);
return 0;
}

P1836HYS与七夕节大作战Accepted
记录信息
评测状态 Accepted
题目 P1836 HYS与七夕节大作战
递交时间 2015-07-31 21:40:25
代码语言 C++
评测机 VijosEx
消耗时间 63 ms
消耗内存 576 KiB
评测时间 2015-07-31 21:40:28
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 9 ms, mem = 572 KiB, score = 10
测试数据 #2: Accepted, time = 4 ms, mem = 568 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 572 KiB, score = 10
测试数据 #4: Accepted, time = 17 ms, mem = 572 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #6: Accepted, time = 1 ms, mem = 572 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #8: Accepted, time = 1 ms, mem = 568 KiB, score = 10
测试数据 #9: Accepted, time = 1 ms, mem = 572 KiB, score = 10
Accepted, time = 63 ms, mem = 576 KiB, score = 100

#include <iostream>
#include <stdio.h>
using namespace std;
int time[10010];
int gf[1010][2];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
double a;
int b;
scanf("%lf%d",&a,&b);
int c=a*100;
gf[i][0]=c;
gf[i][1]=b;
}
for(int i=1;i<=n;i++)
for(int j=10000;j>=gf[i][0];j--)
time[j]=max(time[j],time[j-gf[i][0]]+gf[i][1]);
printf("%d",time[10000]);
}

#include<stdio.h>
#include<string.h>
int dp[1001][10001],p[1001];
int t[1001];
int max(int a,int b)
{
if(a>b)return a;
else return b;
}
int main()
{
int i,j,n;
double m;
scanf("%d",&n);
memset(t,0,sizeof(t));
for(i=0;i<n;i++)
{
scanf("%lf%d",&m,&p[i]);
t[i]=(int)(m*100);
}
for(i=n-1;i>=0;i--)
{
for(j=0;j<=10000;j++)
{
dp[i][j]=(i==n-1?0:dp[i+1][j]);
if(j>=t[i])
{
//printf("get\n");
dp[i][j]=max(dp[i][j],dp[i+1][j-t[i]]+p[i]);
//printf("%d\n",dp[i][j]);
}
}
}
printf("%d",dp[0][10000]);
return 0;
}
没搞懂输出为啥要是五位精度的小数。。。。

代码
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct Girl
{
double im;
int v;
}g[1005];

int n,sum[1005];
double f[5005];

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%d",&g[i].im,&g[i].v);
sum[i]+=sum[i-1]+g[i].v;
}
memset(f,0x7777777f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=sum[i];j>=g[i].v;j--)
f[j]=min(f[j],f[j-g[i].v]+g[i].im);
for(int i=sum[n];i>=0;i--)
if(f[i]<=100)
{
printf("%d\n",i);
break;
}
return 0;
}

这种题懒得往blog上发了。。。
很容易想到倒着算。。
代码
#include <iostream>
using namespace std;
#define INF 1000000000
#define SIZE 1001
int n,sum,get[SIZE];
double spe[SIZE],opt[SIZE*5];
void init()
{
cin>>n;
for (int i = 1; i <= n; i++)
{
cin>>spe[i]>>get[i];
sum += get[i];
}
}
void work()
{
for (int i = 1; i <= sum; i++)
{
opt[i] = INF;
}
sum = 0;
for (int i = 1; i <= n; i++)
{
for (int j = sum; j >= 0; j--)
{
opt[j+get[i]] = min(opt[j+get[i]],opt[j] + spe[i]);
}
sum += get[i];
}
}
int print()
{
for (int i = sum; i >= 0; i--)
{
if ( opt[i] < 100 )
{
cout<<i;
return 0;
}
}
}
int main()
{
init();
work();
print();
return 0;
}

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

var
f,b:array[0..6000]of real;
a:array[0..6000]of longint;
c,d,e,g,h,i,j,k,l,m,n:longint;

function min(a,b:real):real;
begin if a<b then exit(a);exit(b);end;

begin
read(n);
for i:=1 to n do begin read(b[i],a[i]);m:=m+a[i];end;
fillchar(f,sizeof(f),127);
f[0]:=0;
for i:=1 to n do
for j:=m downto a[i] do
f[j]:=min(f[j],f[j-a[i]]+b[i]);
for i:=1 to m do if f[i]<=100.00000001 then h:=i;
writeln(h);
end.
表示真的简单……

反正楼下首届花撸大赛冠军LCS提供思路！
今天刷了一大堆背包，思路都定死了，没有反应到用重要值当做下标做背包。
仔细即可！
dxe

很容易想到反着写，正这写考虑下标不可以，虽然可以将输入的数据A【I】成100000变成整数，但时间上不允许。注意输出按样例的来就可以了，别保留啊！

无聊的来SOFA一下题解。
由于v实在很小 所以我们可以把背包反过来做
f[i]表示价值为i的选择方案所需要的最少的代价，然后就是简单的O1背包啦~

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 492 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 488 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 492 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 492 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 488 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 492 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 488 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 492 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 488 KiB, score = 10
Accepted, time = 45 ms, mem = 492 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1001
#define MAXM 5001
#define inf 1000000000

double f[MAXM];
double t[MAXN];
int v[MAXN];

int n,sum=0;

int main(){
scanf("%d",&n);
for (int i=0;i++<n;){
scanf("%lf%d",&t[i],&v[i]);
sum+=v[i];
}
f[0]=0;
for (int i=0;i++<sum;){
f[i]=inf;
}
for (int i=0;i++<n;){
for (int j=sum;j>=v[i];j--){
f[j]=min(f[j],f[j-v[i]]+t[i]);
}
}
int ans=0;
for (int i=0;i++<sum;){
if (f[i]<=100){
ans=max(ans,i);
}
}
printf("%d\n",ans);
return 0;
}

我的解题报告，大家看一下
http://blog.csdn.net/qq_35904657/article/details/61923526

#include <cstdio>
#include <algorithm>
#define oo 1000000000
using namespace std;

struct node1
{
int v;
double t;
}a[1001];

int main()
{
int n,ans=0,v=0;
double f[5001];
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lf%d",&a[i].t,&a[i].v);
v+=a[i].v;
}
f[0]=0;
for (int i=1;i<=v;i++)
f[i]=oo;
for (int i=1;i<=n;i++)
for (int j=v;j>=a[i].v;j--)
{
f[j]=min(f[j],f[j-a[i].v]+a[i].t);
if (f[j]<=100)
ans=max(ans,j);
}
printf("%d\n",ans);
}

简直爽
```C++
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (1000 + 20)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;

double t[maxn];
int v[maxn];
double dp[10000000 + 50];

int main() {
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
int n,sum = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
scanf("%lf%d",&t[i],&v[i]),sum += v[i];
for(int i = 0;i <= sum;i ++) dp[i] = 1000.0;
dp[0] = 0;
int re = 0;
for(int i = 1; i <= n; i ++) {
for(int j = sum; j >= v[i]; j --) {
dp[j] = min(dp[j],dp[j - v[i]] + t[i]);
if(dp[j] < 100.0) re = max(re,j);
}
}
printf("%d\n",re);
return 0;
}
```

此题有毒。一开始竟然差点被坑了。还好反应过来了。
注意逆向思维~状态描述楼下都已经有了~
直接上代码吧~
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

const int INF=0x7fff;
double f[5000];
int n;
double T=100.0;

int main()
{
double t;
int w;
cin>>n;
for(int i=1;i<=5*n;i++)
f[i]=INF;
for(int i=1;i<=n;i++)
{
cin>>t>>w;
for(int j=n;j>=w;j--)
f[j]=min(f[j],f[j-w]+t);
}
int ans=0;
for(int i=n;i>=0;i--)
if(f[i]<=100)
{ cout<<i<<endl;
break;}
return 0;
}