乐清网站制作,电商设计师联盟网站,外贸业务流程图,盘锦网站建设报价完全背包 有 N 种物品和一个容量是 V 的背包#xff0c;每种物品都有无限件可用。 第 i 种物品的体积是 vi#xff0c;价值是 wi。 求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值。 输入格式 第一行两个整数…完全背包 有 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];int main()
{cin nv;for (int i 1; i n; i ){cinv1[i];cinw[i];}for(int i1;in;i){for(int jv1[i];jv;j){f[j] max(f[j],f[j-v1[i]]w[i]);}}coutf[v];
} 518. 零钱兑换 II
class Solution {
public:int change(int amount, vectorint coins) {vectorint f(amount1,0);f[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){f[j]f[j-coins[i]];}}return f[amount];}
};
377. 组合总和 Ⅳ
//回溯法但超时
class Solution {
public:int count;int sum;int combinationSum4(vectorint nums, int target) {backtracking(nums,target);return count;}void backtracking(vectorint nums,int target){if(sumtarget){count;return;}if(sumtarget){return;}for(int i0;inums.size();i){sumnums[i];backtracking(nums,target);sum-nums[i];}}
}; class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint f(target1,0);f[0]1;for(int j 0;jtarget;j){for(int i0;inums.size();i){if(j-nums[i]0 f[j] INT_MAX - f[j - nums[i]])f[j]f[j-nums[i]];}}return f[target];}
};
