2023年7月31日发(作者：)

01背包问题+例题⽬录QUESTION：有n件物品（每种物品都只有⼀件），w[i]表⽰物品的重量，v[i]表⽰物品的价值，现有⼀个容量为V的背包，应该如何选物品使得书包内装的物品的value之和最⼤呢？

解法：⼆维数组：时间复杂度和空间复杂度都是O(n*V）对于第i个物品，有选和不选两种情况dp[i][j]表⽰在容量为j的情况下选取i个物品的最⼤value值核⼼代码：for(i=0;i=w[i];j--) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);⼀维数组：时间复杂度O(n*V),空间复杂度O(V)核⼼代码：for(i=0;i=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);注意：⽤⼆维数组存的话j的枚举是顺序还是逆序都没有关系但是⽤⼀维数组存的话j的枚举顺序必须是逆序，即从⼤到⼩

举个例⼦：V=8

w[i]v[i]i=123i=234i=345i=456如果按照顺序（j从⼩到⼤枚举),dp数组初始化为0当i=1时dp[2]=max(dp[2],dp[0]+3)=3;dp[3]=max(dp[3],dp[1]+3)=3;dp[4]=max(dp[4],dp[2]+3)=6;dp[5]=max(dp[5],dp[3]+3)=6;当容量为4时，dp[4]的值为6，它是由dp[3]+3的到的，且dp[3]=3，意思是它实际上选了两次“i=1”这个物品，那么结果显然是错的。⽽正巧，顺序枚举j正好完全背包问题的解法（每种物品由⽆穷件）。但是如果逆序枚举的话：dp[5]=max(dp[5),dp[3]+3);dp[5]和dp[3]之前都没有出现过，所以dp[5]=3,值是正确的（dp[3]的值的改变是在dp[5]之后）

例题： 典型的01背包问题ac代码：#include #include #include #include #include #define ll long long int#define maxn 1005using namespace std;int v[maxn],w[maxn],dp[maxn];int main(){ int t,n,V,i,j,ans; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); scanf("%d %d",&n,&V); for(i=0;i=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); printf("%dn",dp[V]); } return 0;

}

2023年7月31日发(作者：)

01背包问题+例题⽬录QUESTION：有n件物品（每种物品都只有⼀件），w[i]表⽰物品的重量，v[i]表⽰物品的价值，现有⼀个容量为V的背包，应该如何选物品使得书包内装的物品的value之和最⼤呢？

解法：⼆维数组：时间复杂度和空间复杂度都是O(n*V）对于第i个物品，有选和不选两种情况dp[i][j]表⽰在容量为j的情况下选取i个物品的最⼤value值核⼼代码：for(i=0;i=w[i];j--) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);⼀维数组：时间复杂度O(n*V),空间复杂度O(V)核⼼代码：for(i=0;i=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);注意：⽤⼆维数组存的话j的枚举是顺序还是逆序都没有关系但是⽤⼀维数组存的话j的枚举顺序必须是逆序，即从⼤到⼩

举个例⼦：V=8

w[i]v[i]i=123i=234i=345i=456如果按照顺序（j从⼩到⼤枚举),dp数组初始化为0当i=1时dp[2]=max(dp[2],dp[0]+3)=3;dp[3]=max(dp[3],dp[1]+3)=3;dp[4]=max(dp[4],dp[2]+3)=6;dp[5]=max(dp[5],dp[3]+3)=6;当容量为4时，dp[4]的值为6，它是由dp[3]+3的到的，且dp[3]=3，意思是它实际上选了两次“i=1”这个物品，那么结果显然是错的。⽽正巧，顺序枚举j正好完全背包问题的解法（每种物品由⽆穷件）。但是如果逆序枚举的话：dp[5]=max(dp[5),dp[3]+3);dp[5]和dp[3]之前都没有出现过，所以dp[5]=3,值是正确的（dp[3]的值的改变是在dp[5]之后）

例题： 典型的01背包问题ac代码：#include #include #include #include #include #define ll long long int#define maxn 1005using namespace std;int v[maxn],w[maxn],dp[maxn];int main(){ int t,n,V,i,j,ans; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); scanf("%d %d",&n,&V); for(i=0;i=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); printf("%dn",dp[V]); } return 0;

}