题目描述

有$n$种物品，每种物品只有一个。第$i$种物品的体积为$v_{i}$，价值为$w_{i}$。选一些物品装到容量为$C$的背包中，问最大的价值是多少？

输入格式

第一行，输入$n,c$

第2至$n+1$行，输入这$n$个物品的体积$v$和价值$w$

输出格式

一个整数，表示最大价值

数据规模与约定

对于$100$的数据，$0<n<200,0<v_i<10000,0<C<10000,0<W<10000$

Code:

#include<bits/stdc++.h>
using namespace std;
int v[101],w[101],dp[10001];
int main()
{
	int n,c;
	cin>>n>>c;
	for(int i=0;i<n;i++)cin>>v[i]>>w[i];
	for(int i=0;i<n;i++)
		for(int j=c-1;j>=v[i]-1;j--)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	cout<<dp[c-1];
	return 0;
}

Hack:

2 0
-1000 -10000
500 20000

正确答案：10000
我的结果：RE