本题选自蓝桥杯 小明的背包1；

用dp[i][j]代表选到第i个物品，剩余空间为j的状态；
用w[i]存放第i件物品的重量；
v[i]存放第i件物品的价值；

对于一件物品我们有两种选择： 要 或 不要；
我们想要两者之见最优（即价值最大）的选法那么就要比较 选此物品前：背包剩余容量为j-w[i]的最大价值+第i件物品的价值v[i] 和 不选此物品价值：背包剩余为j的最大价值，我们取两者较大值作为选完此物品的最大价值。
即：dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);

具体代码如下：

include

include

using namespace std;

define Maxn 5000

int c[Maxn], w[Maxn];
int dp[Maxn];
int C;
// 输入
int n;
int main() {
cin >> n;
cin >> C;
for (int i = 0; i < n; i++) {
cin >> c[i] >> w[i];
}
int dp[Maxn];
memset(dp, 0, sizeof(dp)); //不装满
//创建动态规划数
for (int i = 0; i < n; i++) //遍历每一件物品
{
for (int j = C; j >= c[i]; j--)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
cout << dp[C] << endl;
}

我们不难发现如果从后往前推仅需一个数组即可即dp[j] j代表剩余空间；
先写一个for循环遍历每个物品；
若选择该物品：dp[j]=dp[j-w[i]]+v[i];
不选：dp[j]=dp[j];
我们当然要选两者之间最大值即dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
此时可以改写为：
for(int i=0;i<n;i++) //遍历每一件物品
for(int j=c[i];j<=C;j++)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j]=max(dp[j-c[i]]+w[i],dp[j]);