题目：一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。
给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值
java主要代码：
import java.util.*;
public class Backpack{
public int maxValue(int[] w, int[] v, intn, int cap) {
/*
生成dp[n+1][cap+1]的数组，dp[i][j]表示前i个物品放入包的重量j时的最大价值。
dp[i][j]依赖于i-1，i不放入的话，dp[i][j]=dp[i-1][j],i放入的话，dp[i][j]=dp[i-1][j-w[i]]+v[i],两者
(i放入，那么j-w[i]就要放入)取较大的值为dp[i][j]
0 i=0||w=0
dp[i][j] dp[i-1][j] j<w[i]
max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
*/
/*int[][]dp=new int[n+1][cap+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=cap;j++)
{
if(j<w[i-1])//dp多了一行纯0的,所以dp[1][j]对应w[0],v[0]
{
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);//dp多了一行纯0的，所以
} //相同的物品位置差1
}
}
return dp[n][cap];*/
/*
简化空间，用一维数组存储dp[cap+1]，外层循环0~n来表示物品，在dp[j]是当前状态容量为j的最大价值，内层循环
用倒叙表示才能让dp[j],dp[j-w[i]]+v[i]表示前一个状态的价值。（重复利用dp,一次循环过后，dp内有值了，下次
循环时，比较的是之前的值，比较完之后才更新的）
*/
int[] dp=new int[cap+1];
for(int i=0;i<n;i++)
{
for(int j=cap;j>=w[i];j--)//包里重量要能放下物品，故j>=w[i]
{
dp[j]=dp[j]>dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];
}
}
return dp[cap];
}
}
