2023年8月1日发(作者：)

01背包问题,完全背包问题（递归求解）01背包在选第i个物品时，容积够⽤情况下，只有2种状态可选，放还是不放，找出最⼤价值的选择⽽完全背包在选第i种物品时，容积够⽤情况下，可能有2种以上状态可选，放1个，或者2个，3个，或者不放。找出最⼤价值的选择01背包问题问题

input:5 8 //五件物品 背包容量为84 5 2 1 3 //物品价值3 5 1 2 2 //物品数量output:10 //最⼤价值#includeusing namespace std;int w[100];int v[100];int maxValue;int n,weight;

void dfs(int sum,int nowWeight,int step){ if(nowWeight>weight) //超出重量 则回退

return ; if(step==n) { //已经完成n件物品的选择

if(sum>maxValue)

maxValue=sum; // 更新最⼤价值

return ; } dfs(sum+v[step],nowWeight+w[step],step+1); //选这件物品 dfs(sum,nowWeight,step+1); //不选这件物品

}int main(void){ cin>>n; cin>>weight; for(int i=0;i>v[i]; for(int i=0;i>w[i];

dfs(0,0,0); cout<

#includeusing namespace std;int w[100];int v[100];int maxValue,n,weight;

void dfs(int sum,int nowWeight,int step){ if(nowWeight>weight||step>=n) //当前重量⼤于最⼤重量 或全部选完

return ; //回退

if(sum>maxValue) maxValue=sum; dfs(sum+v[step],nowWeight+w[step],step+1); //选这件物品 然后选下⼀件

dfs(sum+v[step],nowWeight+w[step],step); //选这件物品 然后继续选这⼀件

dfs(sum,nowWeight,step+1); //不选这件物品

}int main(void){ cin>>n; for(int i=0;i>v[i]; for(int i=0;i>w[i]; cin>>weight; dfs(0,0,0); cout<

上述代码的实质是进⾏暴⼒求解 列举每⼀种情况的价值然后进⾏适当的减枝，当然⽤动态规划是更好的⽅法。

2023年8月1日发(作者：)

01背包问题,完全背包问题（递归求解）01背包在选第i个物品时，容积够⽤情况下，只有2种状态可选，放还是不放，找出最⼤价值的选择⽽完全背包在选第i种物品时，容积够⽤情况下，可能有2种以上状态可选，放1个，或者2个，3个，或者不放。找出最⼤价值的选择01背包问题问题

input:5 8 //五件物品 背包容量为84 5 2 1 3 //物品价值3 5 1 2 2 //物品数量output:10 //最⼤价值#includeusing namespace std;int w[100];int v[100];int maxValue;int n,weight;

void dfs(int sum,int nowWeight,int step){ if(nowWeight>weight) //超出重量 则回退

return ; if(step==n) { //已经完成n件物品的选择

if(sum>maxValue)

maxValue=sum; // 更新最⼤价值

return ; } dfs(sum+v[step],nowWeight+w[step],step+1); //选这件物品 dfs(sum,nowWeight,step+1); //不选这件物品

}int main(void){ cin>>n; cin>>weight; for(int i=0;i>v[i]; for(int i=0;i>w[i];

dfs(0,0,0); cout<

#includeusing namespace std;int w[100];int v[100];int maxValue,n,weight;

void dfs(int sum,int nowWeight,int step){ if(nowWeight>weight||step>=n) //当前重量⼤于最⼤重量 或全部选完

return ; //回退

if(sum>maxValue) maxValue=sum; dfs(sum+v[step],nowWeight+w[step],step+1); //选这件物品 然后选下⼀件

dfs(sum+v[step],nowWeight+w[step],step); //选这件物品 然后继续选这⼀件

dfs(sum,nowWeight,step+1); //不选这件物品

}int main(void){ cin>>n; for(int i=0;i>v[i]; for(int i=0;i>w[i]; cin>>weight; dfs(0,0,0); cout<

上述代码的实质是进⾏暴⼒求解 列举每⼀种情况的价值然后进⾏适当的减枝，当然⽤动态规划是更好的⽅法。