接触动态规划的第一题是数塔问题，第二题就是01背包问题了。
当时看的懵懵懂懂，回过头来再看这道题还是非常简单的了。
用 dp[i][j] 表示取前i种物品，使它们总体积不超过j的最优取法取得的价值总和
状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+weight[i])
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
int dp[maxn];
int cost[], weight[]; int main(void)
{
#ifdef LOCAL
freopen("3624in.txt", "r", stdin);
#endif int n, v;
int i;
scanf("%d%d", &n, &v);
memset(dp, , sizeof(dp));
for(i = ; i <= n; ++i)
scanf("%d%d", &cost[i], &weight[i]); int j;
for(i = ; i <= n; ++i)
for(j = v; j >= cost[i]; --j)
{
dp[j] = max(dp[j], dp[j-cost[i]] + weight[i]);
} printf("%d\n", dp[v]);
return ;
}
代码君