商品网站开发需求表,平面设计的范围,网站建设用语,html网页设计作品下载目录 一. 问题描述 二. 题解及代码 一. 问题描述 背包问题(Knapsack problem)是一种组合优化的NP完全问题#xff08;NP完全问题#xff0c;是世界七大数学难题之一#xff09;。 背包问题可以描述为#xff1a;给定一组物品#xff0c;每种物品都有自己的重量和价格… 目录 一. 问题描述 二. 题解及代码 一. 问题描述 背包问题(Knapsack problem)是一种组合优化的NP完全问题NP完全问题是世界七大数学难题之一。 背包问题可以描述为给定一组物品每种物品都有自己的重量和价格在限定的总重量内我们如何选择才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。根据条件不同其具体可以分为01背包基础背包、完全背包、多重背包、分组背包等不同类型的问题具体可以搜索背包九讲。 01背包也称为基础背包是最基本的背包问题说的是一共有 N 件物品每件物品仅有一件第 ii从1开始件物品的重量为w[i]价值为v[i]。在总重量不超过背包承载上限W的情况下求能够装入背包的最大价值是多少并输出具体选择的哪个物品 二. 题解及代码 使用二维数组 dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。每件物品只有两种选择即放或不放放入的话就要判断总价值是否会更大其递推公式及参考代码如下 dp[i][j] Max( dp[i-1][j] dp[i-1][ j-wᵢ ]vᵢ ) #include stdio.h
#includestring.hint backpack[1000][1000];
int wi[1000];
int value[1000];
int x[1000];int main()
{int t;scanf(%d,t);while(t--){int n,j,i,C;scanf(%d%d,n,C);for(i1;in;i)scanf(%d,wi[i]);for(i1;in;i)scanf(%d,value[i]);memset(backpack,0,sizeof(backpack));for(in;i1;i--){for(j0;jC;j){if(jwi[i])backpack[i][j]backpack[i1][j];elsebackpack[i][j]backpack[i1][j](backpack[i1][j-wi[i]]value[i])?backpack[i1][j]:backpack[i1][j-wi[i]]value[i];}}printf(最大值是%d\n,backpack[1][C]);//二维数组倒推输出具体选择物品信息jC;for(i1;in;i){if(backpack[i][j]backpack[i1][j])x[i]0;else{jj-wi[i];x[i]1;}}if(backpack[n][j]0)x[n]0;else x[n]1;for(i1;in;i){if(x[i]!0)printf(%d ,i);}printf(\n);}return 0;
}
