©2020-2024 ioDraw All rights reserved
#include <iostream> using namespace std; #define N 100 //默认有99个物品。第一个不使用 int w[N
]; //每个物品的重量 int v[N]; //每个物品的价值 int n,c; //n：一共有多少物品，c：背包的最大容量 int cw = 0;
//当前放入背包的物品总重量,随着对解空间的不断深入而变化 int cv = 0; //当前放入背包的物品总价值,随着对解空间的不断深入而变化 int
bestv= 0; //最优值；当前的最大价值，初始化为0，满足的话就连同修改储存的最优解 int x[N]; //x[i]=1：物品i放入背包，0代表不放入
int bestx[N]; //最优解；bestx[i]=1代表物品i放入背包，0代表不放入 void input() { cout<<"How many
items ? "; cin>>n; cout<<endl; cout<<"How much capacity ? "; cin>>c; cout<<endl;
cout<<"The weight of items : "; for(int i = 1; i <= n; i++) { cin>>w[i]; } cout
<<endl; cout<<"The value of items : "; for(int i = 1; i <= n; i++) { cin>>v[i];
} cout<<endl; } void output() { cout<<"Maximun capacity: "<<bestv<<endl; cout<<
endl; cout<<"Optimal solution: ( "; for(int i=1;i<=n;i++) cout<<bestx[i]<<" ";
cout<<")"<<endl; } int Bound(int i){//以物品单位重量价值递减顺序装入物品 int cleft=c-cw;//背包剩余容量
int b = cv;//当前已放入的价值 while(i<=n && w[i]<=cleft){//i<=n不越界,w[i]<cleft
表明剩余容量还够，能放 cleft=cleft-w[i]; b=b+v[i]; i++; } if(i<=n)//与上面的while
相比，没有了w[i]<=cleft，还有i<=n，表明没有到达子树，但有cleft的，再挤挤东西进去 b=b+v[i]*cleft/w[i]; return b
; } void backtrack(int t) //回溯函数 参数t表示当前处在第几层做抉择，t=1时表示当前在决定是否将第一个物品放入背包 { if(t>
n) //叶子节点，输出结果 { if(cv>bestv)//如果找到了一个更优的解,保存更优的值和解 { bestv = cv; for(int i=1; i
<=n; ++i) bestx[i] = x[i]; } } else { for(int i=0; i<=1; ++i) //遍历当前节点的子节点：0
不放入背包，1放入背包 { x[t]=i; if(i==0&&Bound(t+1)>bestv)
//左子树，不放入背包i==0，限界函数为Bound有没有潜在可能的比bestv更好的最优值，都满足则进入 { backtrack(t+1); } else {
if(i==1&&(cw+w[t])<=c)//右子树，放入背包i==1，约束函数为放入的物品重量总和不大于背包最大容量，都满足则进入 { cw += w[t]
; cv += v[t]; backtrack(t+1); cw -= w[t]; cv -= v[t]; } } } } } int main() {
input(); backtrack(1); output(); return 0; }