完全背包问题

---

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