网站建设技术知乎,瓷器网站源码,1688黄页大全进口,上海有几个区域01背包问题#xff08;Acwing#xff09; 有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi#xff0c;价值是 wi。 求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值。 输入…01背包问题Acwing 有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 代码二维 #includebits/stdc.h
using namespace std;
const int N 1100;
int n,v;
int v1[N];
int w[N];int f[N][N];int main()
{cin nv;for (int i 1; i n; i ){cinv1[i];cinw[i];}for(int i1;in;i){for(int j0;jv;j){for(int k0;k1;k){ //每件物品最多取几次k就设定为几次if(jk*v1[i]) //能装下k个该物品f[i][j]max(f[i][j],f[i-1][j-k*v1[i]]k*w[i]);}}}coutf[n][v];
} 代码一维
#includebits/stdc.h
using namespace std;
const int N 1100;
int n,v;
int v1[N];
int w[N];int f[N];int main()
{cin nv;for (int i 1; i n; i ){cinv1[i];cinw[i];}for(int i1;in;i){for(int jv;j0;j--){ //一维数组存储需要倒序防止被“污染”for(int k0;k1;k){ //每件物品最多取几次k就设定为几次if(jk*v1[i]) //能装下k个该物品f[j]max(f[j],f[j-k*v1[i]]k*w[i]);}}}coutf[v];
} 我编写的是通用的模板如果每件物品限定了使用次数的时候修改k的限制即可。
416. 分割等和子集
class Solution {
public:bool canPartition(vectorint nums) {int sum0;int nnums.size();for(int i0;in;i){sumnums[i];}if(sum%21) return false;int target sum/2;int f[20010]{0};for(int i0;inums.size();i){for(int jtarget;jnums[i];j--){f[j] max(f[j],f[j-nums[i]]nums[i]);}}if(f[target]target) return true;else return false;}
};
