首页 > 代码库 > 背包问题

背包问题

2024-07-15 12:50:55   228人阅读

问题描述：

有N个物品，每种物品只有一件，每个物品有一个重量w[i],和价值V[i].现在有一个背包容量为C的背包，求问把哪些物品放进背包可以获得最大价值。物品必须保证完整，不得拆分。

解决方案：

代码实现：

#include<stdio.h>#include<algorithm> using namespace std; int N,M,v[50],w[50]; //请输入物品个数N和背包容量限制M,v表示该物品的价值，w表示该物品的重量 int ans,tot; //ans为全局的价值，tot为当前的价值 void dfs(int dep,int now){//now为当前的重量   if(now>M)return;//如果当前背包的重量>背包容量，那么返回   if(dep==N){//如果dep==物品的个数了      ans= max(ans,tot);      return;   }   //选取该物品，把价值记录   tot+=v[dep];  dfs(dep+1,now+w[dep]);   //恢复选取前当前状态   tot-=v[dep];  //不选出该物品   dfs(dep+1,now); } int main(){    //读入物品个数N，背包容量限制M     printf("请输入读入物品个数N，背包容量限制M \n");     scanf("%d%d",&N,&M);    //v表示该物品的价值，w表示该物品的重量      printf("请输入读入物品价值v，物品重量w\n");     for(int i=0;i<N;i++){       scanf("%d%d",&v[i],&w[i]);     }    //令一开始的总价值是0     tot=0;    dfs(0,0);    printf("最大价值是%d\n",ans); }

 


联系
我们