Description
小乐乐辛苦的走到了山脚，却发现山脚多了一个藏宝洞。小乐乐走了进去，无数的化妆品啊！小乐乐眼睛都花了，于是她打开书包开始装。不同的化妆品有不同的价值和不同的大小，每种化妆品只有一个。但是小乐乐的书包很小，最多只能放v体积的东西。小乐乐现在很想知道，她最多能带走多少价值的东西呢？
Input
第一行输入物品数量n(1<n<100) 和 书包体积 v(0<=v<1000)
之后有n行，每行两个数c,val (1<c<100, 1<val<100)表示物品的体积和物品的价值
Output
输出小乐乐能带走的最大的价值
Sample Input
5 10
2 3
5 3
4 5
6 2
4 2
Sample Output
10
**题解:**背包入门题。首先定义一个二维数组，表示 当有i个化妆品，背包容量为j时所能带走的最大价值。
然后，初始化只有一个物品存在时。能带走的价值就是默认的第一个物品的价值
接着开始动态规划，选择n个物品中的第i个（i>1），在背包容量大于等于物品大小时，更新总价值，若在某个容量j(j>=get[i].c)，发现不带这个物品比带这个物品获得的价值更高，那么继承相同容量下带走i-1个物品时获得的最大容量，表示不带走第i个物品，否则，带走i能得到更大的价值，那么就为第i个物品空出get[i].c的空间，并在dp【i】【j】的位置上更新一个最大价值。
这样不断取最优解，并继承下去，最后即可得到dp【n】【v】的最优解，表示有n个物品时容量为v的最大价值是多少
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct worth
{
int c;//体积
int val;//价值
}Get[106];
int main()
{
int i,n,v,dp[105][1005];//dp的是行是化妆品数量，列是最大体积
while(scanf("%d%d",&n,&v)!=EOF)//n件物品，总体积为v
{
memset(dp,0,sizeof(dp));//注意清空数组
for(i=1;i<=n;i++)scanf("%d%d",&Get[i].c,&Get[i].val);
for(i=Get[1].c;i<=v;i++)//初始化第一件化妆品的数据，意思是，在第一行，也就是从第一个物品开始，
dp[1][i]=Get[1].val;///列出来动态规划表格，横行是背包可装的大小，一直在顺序增长，那么拿其中第一个物品，当然是只能放到能装下那个物品的容量
for(int i=2;i<=n;i++)//已经完成初始第一个物品的安排，从第二个物品开始计算
{
for(int j=1;j<=v;j++)//体积却要从1开始计算
{
if(j>=Get[i].c)//注意这里要判断目前最大体积是否大于要装物品的体积，若不够大就不装了直接引用上一个数据
dp[i][j]=max(dp[i-1][j],dp[i-1][j-Get[i].c]+Get[i].val);//其实是找，是减掉当前物品的体积，再装上这个物品，来的划算，还是保持原样不变的体积划算。
else dp[i][j]=dp[i-1][j];
}
}
// for(i=1;i<=n;i++)//动态规划表格真的超美！！！
// {
// for(int j=1;j<=v;j++)
// printf("%5d",dp[i][j]);
// printf("
");
// }
printf("%d
",dp[n][v]);
}
return 0;
}