@[realyanhualengluo](/user/655995)
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int w[101];//时间
int c[101];//价值
int dp[1001];//第i个物品,恰好装满重量为v的背包
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>c[i];
}
//状态转移方程
for(int i=1;i<=m;i++){
for(int v=n;v>=w[i];v--){
dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
}
}
//cout<<dp[n][m];
cout<<dp[n];
return 0;
}
```
数组开小了,循环前后不一致,完全可以去掉一维数组。
by Kevin_Mamba @ 2023-02-23 06:37:29
@[Kevin_Mamba](/user/576934) 最终还是用二维做出来了,主要是二维数组中有些行的一些数是0,导致下一行计算的时候用上一行的数据的时候就会出错。
前面的和你是一样的
```c++
for (int i = 1; i <= m; i++) {
for (int v = 1; v <= n; v++) {//算是优化了,不然应该从0开始
if (v - w[i] < 0) {//背包容量不足之时,只能不装入背包
dp[i][v] = dp[i - 1][v];
}
else {
dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - w[i]] + c[i]);
}
}
}
by realyanhualengluo @ 2023-02-23 22:31:36