欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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));
}

3.4递归、记忆化搜索、动态规划解决01背包问题

记忆化搜索:

#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();
}

3.4递归、记忆化搜索、动态规划解决01背包问题

动态规划:

#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");
}
3.4递归、记忆化搜索、动态规划解决01背包问题
相关标签: 01背包