背包问题学习笔记

时间:2022-02-23 18:43:09

01背包问题

题目描述

一个人有一个最大装载质量为m的背包。现在有n件物品,它们的质量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn。

若每种物品只有一件,求这个人的背包所能装载的最大价值。

输入格式

第一行两个整数m,n,如题中所述。

第2行到第n+1行每行二个整数Wi,Ci,表示每个物品的重量和价值,如题中所叙述。

输出格式

仅一行,为最大的价值。

输入样例

10 4

2 1

3 3

4 5

7 9

输出样例

12

数据范围

m<=200,n<=30

 

求解

  声明一个数组f[j]为总重不超过j的背包的最大价值。于是得到了递推式:

    f[j]=max(f[j],f[j-w[i]]+c[i]),j>=w[i];

  然后大概就是这样推出来的?蒟蒻讲不清楚啊emmmmm直接上代码吧orz

  下面是简单易懂无优化的代码:

 

 

#include <cstdio>
#define MAX_M 200
int n,m,f[MAX_M+5];    //f[i] 存储当背包装载质量为i时的最大价值 
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=1,weight,value;i<=n;i++){    //枚举物品 
        scanf("%d%d",&weight,&value);
        for (int j=m;j>=weight;j--)        //枚举空间。因为使用了滚动数组,而且01背包问题每个物品只能拿一次,所以j要逆序枚举。 
            f[j]=max(f[j],f[j-weight]+value);
    }
    printf("%d",f[m]);    //没有要求恰好放满,所以任何f[i]都是合法的初始状态,最大的方案一定会落在f[i]中 
}  

 

 

  再观察下数据范围,可以略微优化。

  下面是正式代码,加了读入优化,因为数据范围不大就把int改成short了(但是理论上不行的,谁叫这道题数据太水呢嘻嘻嘻)

 

 

#include <cstdio>
#define REG register
#define MAX_M 200
short f[MAX_M+5];    
inline short max(REG short x,REG short y){
    return x>y?x:y;
}
inline short read(){
    REG short ch=getchar(),x=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-')    f=-1;
        ch=getchar();
    } while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}
int main(){
    REG short m=read(),n=read();
    for (REG short i=1,weight,value;i<=n;i++){
        weight=read(),value=read();
        for (REG short j=m;j>=weight;j--)     
            f[j]=max(f[j],f[j-weight]+value);
    }
    printf("%hd",f[m]);    
    return 0;
}  

 

 

 

[参考《挑战程序设计》第二版及网上资料]