骨骼收集器
问题描述
许多年前，在泰迪的家乡，有一个人被称为“骨头收藏家”。这个男人喜欢收集各种各样的骨头，比如狗狗，牛，还有他去了坟墓...... 骨头收集器有一个大容量V的袋子，沿着他的收集之旅有很多骨头，显然，不同的骨骼具有不同的值和不同的体积，现在根据他的行程给出每个骨骼的值，你能计算出骨骼采集器可以得到的总值的最大值吗？
输入
第一行包含整数T，个案数。 接下来是T个案例，每个案例有三行，第一行包含两个整数N，V，（N <= 1000，V <= 1000）表示骨骼的数量和他的包的体积。第二行包含表示每个骨骼值的N个整数。第三行包含表示每个骨骼体积的N个整数。
产量
每行一个整数，表示总值的最大值（此数字将小于2 31 ）。
样本输入
1
5 10
1 2 3 4 5
5 4 3 2 1
样本输出
14
先给大家推荐一个好东西，一个可视化的背包网站，只要你给出数据就能知道中间的运行过程
01背包问题可视化的网站：
01背包无优化版
//N代表数量，V代表背包的容量 //c[i]代表第i个的价值，w[i]代表第i个的体积 int f[N+1][V+1]; memset(f,0,sizeof(f));//初始化 for(int i=1;i<=N;i++){ for(int j=1;j<=V;j++){ if(j>=w[i]){ f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]); } else{ f[i][j]=f[i-1][j]; } } }
01背包一维数组优化版
//N代表数量，V代表背包的容量 //c[i]代表第i个的价值，w[i]代表第i个的体积 int f[V+1]; memset(f,0,sizeof(f));//初始化 for(int i=1;i<=N;i++){ for(int j=V;j>=0;j--){ if(j>=w[i]){ f[j]=max(f[j-w[i]]+c[i],f[j]); } } }
01背包常数优化版
//N代表数量，V代表背包的容量 //c[i]代表第i个的价值，w[i]代表第i个的体积 int f[V+1]; memset(f,0,sizeof(f));//初始化 int sum=0; for(int i=1;i<=N;i++){ sum+=w[i]; int bound=max(V-sum,w[i]); for(int j=V;j>=bound;j--){ if(j>=w[i]){ f[j]=max(f[j-w[i]]+c[i],f[j]); } else{ f[j]=f[j]; } } } 它的优化就是可以减少不必要的计算。
最后把所有的代码给出
#include#include const int N=-1e9+3;using namespace std;int main(){ int N,V; cin >> N >> V; int w[N+1]={ 0,0};//重量 int c[N+1]={ 0,0};//价值 for(int i=1;i<=N;i++){ cin >> c[i]; } for(int i=1;i<=N;i++){ cin >> w[i]; } //N代表数量，V代表背包的容量 //c[i]代表第i个的价值，w[i]代表第i个的体积 int f[V+1]; fill(f,f+V+1,0);//初始化 for(int i=1;i<=N;i++){ for(int j=V;j>=0;j--){ if(j>=w[i]){ f[j]=max(f[j-w[i]]+c[i],f[j]); } } } cout << f[V]; return 0;}