网上购物商城er图_四川建设网官网住房和城乡厅_热搜榜百度一下你就知道_360手机优化大师下载

1.0-1背包：

经典问题(最大价值)：

        二维数组:

// 先遍历物品，再遍历背包。遍历顺序可以交换。
for(int i = 1;i < kinds;i++){for(int j = 0;j <= bagweight;j++){if(weight[i] > j) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}
}

        滚动数组:

// 先遍历物品，再遍历背包，而且背包得倒着遍历，顺序不能变
for(int i = 0;i < kinds;i++){for(int j = bagweight;j <= weight[i];j--){dp[j] = max(dp[j],dp[j-weight[i]+value[i]]);}
}

方案问题(怎么把背包装满):

// 初始化
vector<int> dp (bagweight+1,0);
dp[0][0] = 1;
if(nums[0] <= bagweight) dp[0][nums[0]] = 1;// 先遍历物品再遍历背包
for(int i = 1;i < kinds;i++){for(int j = 0;j <= bagweight;j++){if(j < nums[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]];}
}

2.完全背包：

经典问题(最大价值):

// 遍历顺序：二者皆可
for(int i = 1;i < kinds;i++){for(int j = 0;j < bagweight;j++){if(j < weight[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}
}

方案问题：

        二维数组：

// dp初始化
for(int j = 0;j < bagweights;j++){if(j % weight[0] == 0) dp[0][j] = 1;
}
for(int i = 0;i < kinds;i++){dp[i][0] = 1;
}// 遍历顺序都可以
for(int i = 1;i < kinds;i++){for(int j = 1;j <= weights;j++){if(j < nums[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];}
}

        滚动数组：

// dp初始化
dp[0] = 1;// 遍历顺序：先遍历物品再遍历背包
for(int i = 0;i < kinds;i++){for(int j = nums[i];j <= bagweight;j++){if(dp[j]+dp[j-nums[i]] <= INT_MAX) dp[j] += dp[j-nums[i]];}
}