这两天继续练习动态规划，对于背包问题进行了针对化练习。
题目：
背包最大重量为4。
物品为：
重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
问背包能背的物品最大价值是多少？
首先考虑采用暴力解法，每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n),这里的n表示物品数量。这样必定会超时。
采用动态规划解法可以将时间复杂度降到n2,空间复杂度也为n2，代码如下：
public class Solution {
int[][] dp;
public int bag01(int[][] goods,int size){
dp=new int[goods.length][size+1];
for (int i = 0; i < size+1; i++) {
if (i>=goods[0][0]){
dp[0][i]=goods[0][1];
}
}
for (int i = 1; i < goods.length; i++) {
for (int j = 1; j < size+1; j++) {
int temp1=dp[i-1][j];
int temp2=0;
if (j>= goods[i][0]){
temp2=dp[i][j-goods[i][0]]+goods[i][1];
}
if (temp1>temp2){
dp[i][j]=temp1;
}else {
dp[i][j]=temp2;
}
}
}
for (int i = 0; i < goods.length; i++) {
for (int j = 0; j < size+1; j++) {
System.out.print(dp[i][j]+" ");
}
System.out.println("");
}
return dp[goods.length-1][size];
}
}
