使用回溯算法编写一段C++代码并且进行剪枝优化, 问题描述:给定 n 个物品和一个容量为 C 的背包,请给出物品装 入背包的方案,使得背包中物品的总价值 M 最大,并满足: •…
- User
使用回溯算法编写一段C++代码并且进行剪枝优化, 问题描述:给定 n 个物品和一个容量为 C 的背包,请给出物品装 入背包的方案,使得背包中物品的总价值 M 最大,并满足: • 每个物品 I 的重量为 wi,价值为 vi。 • 每个物品可拆分,背包中物品的总重量不能超过容量 C
- Assistant
#include<bits/stdc++.h> using namespace std;
const int MAXN=1005;//物品个数上限 int n,C;//物品数量,背包容量 int w[MAXN],v[MAXN];//w[i]表示第i件物品的重量,v[i]表示第i件物品的价值 int ans;//记录最大价值 int cnt[MAXN];//cnt[i]表示已选择第i个物品的数量(可拆分) bool vis[MAXN];//标记第i个物品是否已经被选择过
void dfs(int curW,int curV){//当前所选物品总重curW,总价值curV if(curW>C) return;//超出背包容量直接剪枝 ans=max(ans,curV);//更新最大价值 for(int i=1;i<=n;++i){ if(cnt[i]==0 && vis[i]==0){//如果第i个物品未被选且未被选择过,则可以选择它 cnt[i]++; dfs(curW+w[i],curV+v[i]); cnt[i]--;//选择完毕,将其恢复原状 } else if(cnt[i]>0 && vis[i]==0){//如果第i个物品可拆分且未被选择过,则可以不断选择它 cnt[i]++; dfs(curW+w[i],curV+v[i]); cnt[i]--; } } }
int main(){ cin>>n>>C; for(int i=1;i<=n;++i) cin>>w[i]>>v[i]; dfs(0,0);//从起始状态开始搜索 cout<<ans<<endl;//输出最大价值 return 0; }