求一道01背包题的AC代码及解释
斯克提斯的鸦人时间限制：1000 ms | 内存限制：65536 KB
描述
据说斯克提斯的鸦人们非常喜欢一种叫做泰罗果的食物。每天早上他们都会派出一个鸦人去采泰罗果。
每个鸦人都有一个背包，有一定的容量。而鸦人们对每个泰罗果的价值定义也有一定的规则。泰罗果越小价值越高。每一个鸦人都希望一次能采到价值最大的泰罗果。
输入
多组测试数据
每组数据3行，第一行2个整数 n (0 <= n <=10000 ), w (0 <= w <=500000 )。表示宝石个数和背包空间。
第二行n个整数vi (i=1,2,……n)，表示第i个宝石的价值。(0<= vi <=10000)
第三行n个整数ti (i=1,2,……n)，表示第i个宝石的体积。(1<= ti <= w）
数据以-1 -1结束，不必输出结果。
输出
对每一组数据输出一个整数，即能够采到的泰罗果的最大价值。
样例输入
4 7
2 3 4 5
5 4 3 2
-1 -1样例输出
9
我的代码：
程序代码：#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int w[10003];
int val[10003];
long long c[500003];
int main() {
int num,vol;
long long index;
while(cin >> num >> vol) {
if(num==-1) {
return 0;
}
for(int i = 1; i <= num ; i++) {
scanf("%d",&val[i]);
}
for(int i = 1; i <= num; i++) {
scanf("%d",&w[i]);
}
memset(c,0,sizeof(c[0])*(num + 2));
index = 0;
for(int i = 1; i <=num; i++) {
for(int j =((index + w[i])<500000?index+w[i]:500000); j - w[i] >= 0; j--) {
if(c[j] < c[j-w[i] ]+ val[i])
c[j] = c[j-w[i]] + val[i];
}
index+=w[i];
}
cout << c[vol] << endl;
}
return 0;
}
我用的自滚动数组，但还是超时，不知道问什么，求AC代码
提交地址http://www.
