合肥营销网站建设联系方式,html网页制作流程,产品推广营销方案,南京龙媒网络科技有限公司可行性判定
当前有 N 件物品和一个容积为 V 的背包。
已知第 i 件物品的体积是 ci#xff0c;每种物品有且仅有一件#xff0c;每一件物品能够选择放或者不放入背包。
现在我们不考虑物品的价值#xff0c;只关心是否能够取出若干个物品#xff0c;恰好使这个背包被装…可行性判定
当前有 N 件物品和一个容积为 V 的背包。
已知第 i 件物品的体积是 ci每种物品有且仅有一件每一件物品能够选择放或者不放入背包。
现在我们不考虑物品的价值只关心是否能够取出若干个物品恰好使这个背包被装满。
也就是说现在我们需要选出若干件物品使它们的体积之和 恰好为 V 。
dp 数组初始化
普通的 01 背包中要求放入物品的体积之和不超过 V而现在我们需要使体积之和恰好为 V。
因为结果只需要输出 V 这个体积是否能被组出因此我们可以将 dp 数组定义成bool类型。
令 dp[i][j] 表示前 i 个物品中取出若干个物品体积之和为 j 的可行性当可行的时候 dp[i][j] 等于 11否则等于 00。在最开始背包里空空如也的时候背包里物品的体积之和没有物品为 00所以 00 这个状态在开始就是合法的。当要求选出物品体积之和恰好为 V 的条件下唯一可行的转移路线是从 dp[0][0]→dp[N][V]即dp[0][0] 是唯一可行的起点。所以应当先将整个dp数组初始化为 00 再将 [0][0]dp[0][0] 修改为 11 。
核心代码
dp[0][0] 1; // 初始化开始时唯一的合法状态
for (int i 1; i N; i) {for (int j 0; j V; j) {if (j c[i]) { // 如果容积小于当前物品的体积dp[i][j] dp[i - 1][j]; // 直接从上一层转移} else if (dp[i - 1][j] || dp[i - 1][j - c[i]]){// 如果前 i - 1 个物品已经能凑出体积之和为 j// 或者前 i - 1 个物品已经能凑出体积之和为 j - c[i] , 那个当前物品加入可以使体积之和变为 jdp[i][j] 1; // 此时前 i 个物品能够凑出体积之和为 j}}
}
时间复杂度为 O(NV)空间复杂度为 O(NV)。
空间优化
dp[0] 1;
for (int i 1; i N; i) {for (int j V; j c[i]; j--) {dp[j] | dp[j - c[i]];}
}
完整代码
#include iostream
using namespace std;bool dp[110][1010];
int c[110];int main() {int N, V;cin N V;for (int i 1; i N; i) {cin c[i];}dp[0][0] 1;for(int i 1; i N; i){for(int j 0; j V; j){if (j c[i]){dp[i][j] dp[i - 1][j];} else if (dp[i - 1][j] || dp[i - 1][j - c[i]]){dp[i][j] 1;}}}if (dp[N][V]){cout Yes endl;} else {cout No endl;}return 0;
}
