问题描述：
给定n个物品，每个物品的重量为wi，价值为vi，问容量为c的背包最多能装多大价值的东西。
思想：设dp(i,j)表示用j容量的背包，装前i个物品的所能装的最大价值。
根据能不能装进去第i个物品，可分为f(i,j)的值可分为两大情况：
①能装进去（w[i] <= j） ：dp[i][j] = max( dp[i - 1][j - wi] + v[i] , dp[i - 1][j] )
②不能装进去（w[i] > j）: dp[i][j] = dp[i-1][j]
代码如下
#include<bits/stdc++.h> using namespace std; int dp[50][50]; int main(){int s;//获得的最大价值 int w[5] = {2,2,6,5,4};//物品的重量 int v[5] = {6,3,5,4,6};//物品的价值 int x[5];//物品的选取状态 int n = 5; int C=10;//背包最大容量 //初始化dpfor(int i = 0;i <= C;i++){ //当没有物品时，任何容量价值均为0dp[0][i] = 0;}for(int i = 0;i <= n;i++){ //当容量为0时，任何物品都装不进去，价值为0dp[i][0] = 0;}//开始迭代for(int i = 1;i <= n;i++){for(int j = 1;j <= C;j++){if(w[i - 1] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i - 1]] + v[i - 1]);}}}//物品重量for(int i = 0;i < n;i++){cout<<w[i]<<" ";}cout<<endl;//物品价值for(int i = 0;i < n;i++){cout<<v[i]<<" ";}cout<<endl;//价值cout<<"最大价值："<<dp[5][10];cout<<endl;//判断哪些物品被选了int j = C;for(int i = n;i >= 1;i--){if(dp[i][j] > dp[i - 1][j]){x[i - 1] = 1;j = j - w[i -1];}else{x[i - 1] = 0;}}for(int i = 0;i < n;i++){cout<<x[i]<<" ";}return 0; }
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
