围观
by NeilKleist @ 2016-12-15 20:48:43
###**同问**
by wawcac @ 2016-12-16 11:40:17
可怜的萌新没人回复QAQ
by jzjerry @ 2016-12-19 00:06:57
```cpp
#include<stdio.h>
int best[1010][110];
int c,total;
int weight[110],value[110];
int i,j;
int max(int x,int y)
{
return (x>y)?x:y;
}
int main()
{
scanf("%d%d",&c,&total);
for(i=0;i<total;i++)
{
scanf("%d%d",&weight[i],&value[i]);
}
for(i= total - 1;i>=0;i--)
{
for(j=0;j<=c;j++)
{
if(j < weight[i])
{
best[i][j]=best[i+1][j];
}
else
{
best[i][j]=max(best[i+1][j-weight[i]]+value[i],best[i+1][j]);
}
}
}
printf("%d\n",best[0][c]);
return 0;
}
```
你这个递推式 是自底向上（逆向的）。具体可以自己手写一个图表看一下。
by LYFer @ 2016-12-19 21:28:37
@ Li\_Yi\_Fan 十分感谢！我再自己研究一下，按我的想法的话递推方向应该影响不大，总之我先试着自己推一下吧。
再次感谢！
by jzjerry @ 2016-12-20 11:59:30
发现具体问题了，递推过程中数组有越界
by jzjerry @ 2016-12-22 21:09:47
```cpp
#include <bits/stdc++.h>
using namespace std;
int w[1000],v[1000],dp[1000][1000];
int main()
{
int n,m,i,j;
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for (int i=1;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if ((j-w[i]>=0) && (dp[i-1][j-w[i]]+v[i]>dp[i][j]))
dp[i][j]=dp[i-1][j-w[i]]+v[i];
}
}
cout<<dp[n][m];
return 0;
}
```
by znwyx @ 2017-01-19 15:51:29
@jzjerry
by znwyx @ 2017-01-19 15:54:16