https://www.cnblogs.com/A1269180380/p/6344043.html
- 注意数组的遍历方向跟01相反是从左往右。
- 状态转移方程
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}
输入:
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
物品号i 1 2 3 4 5 6
体积C 3 2 5 1 6 4
价值W 6 5 10 2 16 8
output:26
6 10
3 6
2 5
5 10
1 2
6 16
4 8
输出:
仅一行，一个数，表示最大总价值。
#include <bits/stdc++.h>
using namespace std;
int main(){
int i,j,number,volumn;
scanf("%d %d",&volumn,&number);
int weight[100]; //记录每个物品的质量
int value[100]; //记录每个物品的价值
int v,w;
int f[100]; // 记录value的数组
bool path[100][100]={false}; // 记录路径
for(i=0;i<100;i++){
f[i]=0;
}
for(i=1;i<number+1;i++){
scanf("%d %d",&w,&v);
weight[i]=w;
value[i]=v;
}
for(i=1;i<=number;i++){
for(j=weight[i];j<=volumn;j++){ // 必须从0开始，因为j-weight[i]会等于0
if(j-weight[i]>=0&&f[j]<f[j-weight[i]]+value[i]){
path[i][j]=true;
f[j]=f[j-weight[i]]+value[i];
}
}
}
cout<<endl;
cout<<"最优值:"<<f[volumn]<<endl;
cout<<"打印选中的节点:"<<endl;
while(i>=1&&volumn>=0){
if(path[i][volumn]==true){
cout<<"weight:"<<weight[i]<<" num:"<<1<<endl;
volumn-=weight[i];
}
else{
i--;
//cout<<0<<"\t";
}
}
}
