Dynamic-programming-DP-backpack.rar_dp算法

#include<iostream> using namespace std; #define n 4 //暂定只有四种物品 #define MAX 61 int m[MAX][MAX]; int v[MAX]; //每个物品的重量 int w[MAX]; //每个物品的价值 int M; //背包容量 int max(int x,int y) { if(x>y) return x; else return y; } void knapsack() { for(int j=0;j<=M;j++) { if(j<w[n]) m[n][j]=0; else m[n][j]=v[n]; } for(int i=n;i>=1;i--) for(j=0;j<=M;j++) { if(j<w[i]) m[i][j]=m[i+1][j]; else m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } cout<<"最优解为:"<<m[1][M]<<endl; } void main() { cout<<"请输入背包容量(不超过60):"<<endl; cin>>M; cout<<"请依次输入每个物品的价值:"<<endl; for(int i=1;i<=n;i++) cin>>v[i]; cout<<"请依次输入每个物品的重量:"<<endl; for(i=1;i<=n;i++) cin>>w[i]; knapsack(); }