问题如下：
问题描述：
给定n个重量为wi,价值为vi的物品（i=1,2,…,n），以及一个重量为W的背包，找出其中最有价值的物品子集，并且能全部放入背包中。
输入样例：（第一行是背包重量上限，第二、三、四、五行是物品的重量和价值）
10
7 42
3 12
4 40
5 25
输出样例：（能够放入背包的物品最大价值）
65
代码如下：
#include <iostream> #include <algorithm>//max()函数头文件 #include <cstring>//memset函数头文件 using namespace std; #define N 100 int main(){ int dp[N][N]; memset(dp,0,sizeof(dp)); int n=4;//共四件物品 int BagMax;cin>>BagMax;//输入背包最大容量 int height[N];int value[N];//物品重量数组，物品价值数组 int MaxValue=0; for(int i=1;i<=n;i++){//应该从1开始，下方初始化操作dp[i][j]=dp[i-1][j]; i需要>=1 cin>>height[i]>>value[i];//输入物品的重量、价值 } for(int i=1;i<=n;i++){//仅对i个物品选择 for(int j=0;j<=BagMax;j++){//穷尽背包空间 dp[i][j]=dp[i-1][j];//初始化 if(height[i]<=j){//第i个物品重量在背包可容纳范围内 dp[i][j]=max(dp[i-1][j],dp[i-1][j-height[i]]+value[i]); if(dp[i][j]>MaxValue){MaxValue=dp[i][j];} } } } cout<<MaxValue<<endl; return 0; }
