Problem I 万神的竞赛
现有 n 门竞赛,万神可以参加每门竞赛至多 1 次。参加第 i 门竞赛会花费
万神 w i 点体力,并增加万神的智商 v i 点。万神共有 W 点体力,那么万神通过
参加竞赛,至多能增加多少智商呢?
输入格式
输入包含多组数据(至多 20 组,其中大数据不超过 10 组),请处理到文件结束。
每组数据,第 1 行包含 2 个整数 n, W ,用空格分割。
之后 n 行,第 i 行包含整数 w i , v i ,用空格分割。
保证 0 ≤ n ≤ 1000,0 ≤ W ≤ 10 8 , 0 ≤ w i ≤ 10 6 , 0 ≤ v i ≤ 50。
输出格式
对于每组数据输出 1 行,表示万神能增加的智商的最大值。
输入样例
3 4
1 5
2 4
3 3
输出样例
9
样例解释
最优解显然是参加第 1 和第 2 门竞赛。
思路：（大重量，小价值背包）
很显然的01背包么～～～但是，但是，数据量有点大啊，，数组本地开的下，
128M 要开 1e8 个int 只够开1/4提交上去超内存，估计不超内存也超时了o(n*W) 想来想去，，，懵逼了，请教了一下师兄一下，发现p[i] * 1000 <= 50000这数不大，转换成了，在某一价值下，求背包最小容量，拿这道题来说，求在获得某点智商的情况下，需要最少的体力是多少，从而轻松的解决问题，
最后一重for找到第一个小于等于总体力的状态，能达到的最大智商．
代码：
/*************************************************************************
> File Name: te.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年04月21日 星期四 22时51分56秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1006;
int W[N], V[N];
int dp[N*50];
int main()
{
int n, w;
while(~scanf("%d%d", &n, &w))
{
int sum = 0;
for(int i=0; i<n; i++)
{
scanf("%d%d", &W[i], &V[i]);
sum += V[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i=0; i<n; i++)
for(int j=sum; j>=V[i]; j--)
dp[j] = min(dp[j-V[i]]+W[i], dp[j]);
for(int i=sum; i>=0; i--)
if(dp[i] <= w)
{
printf("%d\n", i);
break;
}
}
return 0;
}
最后两道 K， L 没有ac ,鄙人才学疏浅，未能参悟透其中奥妙．还望高人指点，长路漫漫任重道远．．．．．