DP 一直是心中痛，不多说了，这个暑假就坑在这上了。
这暑假第一道DP题，01背包问题。
题意是说物品有 重量和价值 ，但你能承受的重量有限，问你能带的最大价值。
这题数组开大点，尽管不知道有啥坑点，可是我数组开得大，直接1A了。
想想自己DP都是大问题，还要给学弟讲（tiao）题（jiao），真是忧伤。
仅仅能这几天通宵点出 DP 天赋。顺便贴上自己的理解，反正我也准备这样给学弟讲，假设有误，请路过大神指正。
论01背包的自我修养：
N个物品，M容量的包，最大价值为W。
第 i
件物品分别有 Vi 的重量和 Ci
的价值。
N = 4 ，M= 6 。
V C
1： 1 4
2： 2 6
3： 3 12
4： 2 7
int dp[10001],c[10001],v[10001];
//分别为背包的价值，物品的价值，物品重量。
memset(dp,0,sizeof(dp));
//初始化背包 毕竟没放东西的时候是没有价值的
//还有其它初始化为-INF 的情况，仅仅有dp[0]=0。这是要求：恰好装满的最大价值。
for ( int i = 0 ; i < n ; i++)
{
//从第一件物品開始放
for ( int j = m ; j-v [i] >= 0 ; j--)
// j - v[i] >=0防止数组越界，毕竟背包容量不能为负
{
//背包每次减去1，看能不能放进去这件物品
//printf("%d:max(%d,%d) ",j,dp[j],dp[j-c[i]]+v[i]);
dp[j] = max ( dp[j] , dp[ j-v[i] ] + c[i] );
//当背包容量为j的时候，能放进去添加价值，就放进去
//dp[j] 容量为j的时候的价值
//dp[ j-c[i] ] + c [i]
（容量j减去当前物品的重量=剩余容量） 的价值 + 当前物品的价值
//价值当然越大越好
取max
//当 j - v[i] < 0表明背包已经不能放了。
}
}
容量：max（前一个价值，放入当前物品后的价值）
6 :max(0,4) 5 :max(0,4) 4 :max(0,4) 3 :max(0,4) 2 :max(0,4) 1 :max(0,4)
6 :max(4,10) 5 :max(4,10) 4 :max(4,10) 3 :max(4,10) 2 :max(4,6)
6 :max(10,22) 5 :max(10,18) 4 :max(10,16) 3 :max(10,12)
6 :max(22,23) 5 :max(18,19) 4 :max(16,13) 3 :max(12,11) 2 :max(6,7)
最后背包 从容量 0 ~ 6 所能有的价值，取其最大值。
M：W 0 1 2 3 4 5 6
0:0 1:4 2:7 3:12 4:16 5:19 6:23
这时候背包装满的情况 价值W最大，为23。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int dp[1000001];
int c[100001],v[100001];
int n,m; int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d",&c[i],&v[i]);
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=m;j-c[i]>=0;j--)
{
dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
}
}
int ans=0;
for(int i=0;i<=m;i++)
ans=max(ans,dp[i]);
printf("%d\n",ans);
}
}