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; }
[参考《挑战程序设计》第二版及网上资料]