2023年8月1日发(作者：)
01背包问题浅谈#递归算法问题描述：
对于给定的i个物品，每个物品有对应的价值v[i],和体积w[i],现有容积为k的背包，试求能装的总价值最⼤的物品的组合。问题分析：1.对于给定的前N个物品，⽤容积为K的背包来装。为了得到最优解我总要从第N-1个物品的最优解递推到第N个。第N个物品的价值和体积⽤数组v和w表式； Load_Bag(N,K)表述考虑⽤容积为K的bag装前N个物品。2.（1）容积K装不下第N个物品，则此时我们只好⽤容积为K的背包装前N-1个物品 （2）容积K装得下第N个物品，则我们考虑装不装第N个物品 ①装：若要装第N个物品则我们要腾出w[N]的空间再装⼊第N个物品，Load_Bag(N,K)=Load_Bag(N-1,K-w[N])+v[N] ②不装：和情况（1）相同int Load_Bag(int i,int capacity){ if(i==0||capacity==0){ return 0;//如果考虑装⽤容量为capacity的背包装0个物品或者⽤0容量的背包装i个物品，所得价值为0
} else{ if(capacity } else{ return max(Load_Bag(i-1,capacity),(Load_Bag(i-1,capacity-w[i])+v[i]));//分两种情况，考虑装第i个物品，或不装 } }} 打表出来看看#include int Load_Bag(int i,int capacity){ if(i==0||capacity==0){ return 0;//如果考虑装⽤容量为capacity的背包装0个物品或者⽤0容量的背包装i个物品，所得价值为0 } else{ if(capacity } else{ return max(Load_Bag(i-1,capacity),(Load_Bag(i-1,capacity-w[i])+v[i]));//分两种情况，考虑装第i个物品，或不装 } }}int main(){ int n,k;//⼀共有n个物品，背包容量为k cin>>n>>k; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } for(int i=0;i<=n;i++){ for(int j=0;j<=k;j++){ cout< 2023年8月1日发(作者：) 01背包问题浅谈#递归算法问题描述： 对于给定的i个物品，每个物品有对应的价值v[i],和体积w[i],现有容积为k的背包，试求能装的总价值最⼤的物品的组合。问题分析：1.对于给定的前N个物品，⽤容积为K的背包来装。为了得到最优解我总要从第N-1个物品的最优解递推到第N个。第N个物品的价值和体积⽤数组v和w表式； Load_Bag(N,K)表述考虑⽤容积为K的bag装前N个物品。2.（1）容积K装不下第N个物品，则此时我们只好⽤容积为K的背包装前N-1个物品 （2）容积K装得下第N个物品，则我们考虑装不装第N个物品 ①装：若要装第N个物品则我们要腾出w[N]的空间再装⼊第N个物品，Load_Bag(N,K)=Load_Bag(N-1,K-w[N])+v[N] ②不装：和情况（1）相同int Load_Bag(int i,int capacity){ if(i==0||capacity==0){ return 0;//如果考虑装⽤容量为capacity的背包装0个物品或者⽤0容量的背包装i个物品，所得价值为0 } else{ if(capacity } else{ return max(Load_Bag(i-1,capacity),(Load_Bag(i-1,capacity-w[i])+v[i]));//分两种情况，考虑装第i个物品，或不装 } }} 打表出来看看#include int Load_Bag(int i,int capacity){ if(i==0||capacity==0){ return 0;//如果考虑装⽤容量为capacity的背包装0个物品或者⽤0容量的背包装i个物品，所得价值为0 } else{ if(capacity } else{ return max(Load_Bag(i-1,capacity),(Load_Bag(i-1,capacity-w[i])+v[i]));//分两种情况，考虑装第i个物品，或不装 } }}int main(){ int n,k;//⼀共有n个物品，背包容量为k cin>>n>>k; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } for(int i=0;i<=n;i++){ for(int j=0;j<=k;j++){ cout<
发布评论