3.4递归、记忆化搜索、动态规划解决01背包问题
程序员文章站
2022-05-12 15:52:55
...
递归:
自顶向下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int w[100],v[100],flag[100];
int knapsack(int n,int c){
if(n==0||c==0){
return 0;
}
else if((c>=w[n])&&(knapsack(n-1,c)<(knapsack(n-1,c-w[n])+v[n]))){//要选第i个
return knapsack(n-1,c-w[n])+v[n];
}
else{
return knapsack(n-1,c);
}
}
int main(){
int n,c;//个数,和最大容量
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
}
printf("可选的最大价值是:%d\n",knapsack(n,c));
}
自底向上:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int w[100],v[100],flag[100],n,c;
int rec(int i,int j){
int res;
if(i==n+1)res=0;
else if(j<w[i])res=rec(i+1,j);
else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
return res;
}
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
}
printf("可选的最大价值是:%d\n",rec(1,c));
}
记忆化搜索:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,c,w[100],v[100],flag[100],dp[100][100000];
int knapsack(int n,int c){
if(n==0||c==0){
return 0;
}
if(dp[n][c])return dp[n][c];
else if((c>=w[n])&&(knapsack(n-1,c)<(knapsack(n-1,c-w[n])+v[n]))){//要选第n个
dp[n][c]=knapsack(n-1,c-w[n])+v[n];
return dp[n][c];
}
else{
dp[n][c]=knapsack(n-1,c);
return dp[n][c];
}
}
void print(){
int a=c;
for(int i=n;i>=1;i--){
if(dp[i][a]>dp[i-1][a]){//说明选了
flag[i]=1;a-=w[i];
}
}
for(int i=1;i<=n;i++){
printf("%3d",flag[i]);
}
printf("\n");
}
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
}
printf("可选的最大价值是:%d\n所选的物品情况是:\n",knapsack(n,c));
print();
}
动态规划:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int w[100],v[100],x[100],m[100][100000];
int main(){
int n,c;//个数,和最大容量
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
}
int jMax=min(w[n]-1,c);
//以下两行相当于填表m的最后一行
for(int j=0;j<=jMax;j++)m[n][j]=0;
for(int j=w[n];j<=c;j++)m[n][j]=v[n];
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++)m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
//以下两行相当于填表,第一行只用填:m[1][c]
m[1][c]=m[2][c];
if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
int a=c;
for(int i=1;i<n;i++){
if(m[i][a]==m[i+1][a])x[i]=0;
else {x[i]=1;a-=w[i];}
}
x[n]=(m[n][c])?1:0;
printf("可选的最大价值是:%d\n所选的物品情况是:\n",m[1][c]);
for(int i=1;i<=n;i++){
printf("%3d",x[i]);
}
printf("\n");
}
上一篇: 最大间隔
下一篇: luogu P2664 树上游戏