背包问题1（01背包）
N件物品，没见有重量Wi，价值Vi；选其中几件放入容量为M的背包中，求价值的最值。——经典背包问题
背包问题分三类：
1.01背包：每件物品仅一件，可以不将背包装满（要么取0件要么1件）
2.完全背包：每件物品无限件，可以不将背包装满。
3.多重背包：每件物品可一定数量件，可不将背包装满。
此片详解01背包。
建一个N*（M+1）的数组dp[N][M]，物品从第一个开始遍历依次装入背包。
行下标从0到N - 1，表示从第一种物品装到底N - 1中物品，列从0到M，表示包中物品重量从0到M。
关键公式：dp [ i ] [ j ] = max / min ( dp [ i - 1 ] [ j ] , dp[ i - 1 ] [ j - W[ i ] ] + V [ i ] ) ;
这个公式什么意思呢？max/min是根据题目不同选择采取最大或最小值。主要是看()中的部分。dp[i - 1][ j ]指包内重量为j，但是包中不包含第i种物品。dp[i - 1][j - w[ i ]] + v[ i ]指的是包内装有第i种物品，那么这种情况下，包内总重量为j的情况下前i - 1中物品的重量就应该是j减去当前物品的重量，物品价值就应该是前i - 1种物品的总价值加上当前物品的价值，那么最大或最小价值就是包内装当前物品和不装当前物品两种情况中的最值。
典例：http://acm.hdu.edu.cn/showproblem.php?pid=2602
题意：可理解为背包问题，一共n样物品各有其重量w[ i ]和价值v[ i ]，给出背包容量m求出背包所容最大的价值。
分析：每件物品放入或不放入背包，若不放入背包，则dp[ i ] [ j ]的值即为dp[ i - 1 ] [ j ]。若是放入背包，则需要在当重量为 j - w[ i ] 的基础上加入物品 i，价值也应是在dp[ i ] [ j - w [ i ] ] 的值上再加上物品 i 的价值v [ i ] ，其价值即为dp[ i - 1 ] [ j - w[ i ] ]+ v[ i ] 。再取两个之中的较大者即得到最优解。
代码实现：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int w[1005],v[1005],dp[1005][1005];
int main()
{
int T,n,m;
cin>>T;
while(T--)
{
cin>>n>>m;
//注意先输入价值！因为这个WA好几次
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
cin>>w[i];
memset(dp,0,sizeof(dp));//dp数组初始化
for(int i=1;i<=n;i++) //物品从第一个开始遍历
{
for(int j=0;j<=m;j++)//质量从0开始，数据有重量为0，价值不为零的情况
{
//能装下w[i]时，比较dp[i-1][j]和dp[i-1][j-w[i]]+v[i]
if(w[i]<=j) {dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}
//装不下则dp[i][j]=dp[i-1][j]
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}
