7-1 0-1背包 分数 25 作者 郑琪 单位 广东外语外贸大学
给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
5 10
2 6
2 3
6 5
5 4
4 6
输出样例:
15
/*
m[i][j]=max{m(1+1,j),m(i+1,j-w[i])+vi} j>=w[i];
m[i][j]=m[[i+1][j] 0<=j<w[i];
边界条件： m[n][j]=v[n] j>=w[n];
m[n][j]=o 0<=j<w[n]
*/
#include<iostream>
using namespace std;
int n,C;//n:物品个数 C:背包最大容量
int v[101],w[1001],m[101][1001];//m(i,j) 表示背包可用容量为j(1<=j<=w),已考虑物品 1,2,3, ... ,i(1<=i<=n) 时的最优解的值。
int dp(){
for(int j=0;j<=C;j++){//背包剩余容量为j
if(j>=w[n]) m[n][j]=v[n];//
else m[n][j]=0;//物品比背包大
}
for(int i=n-1;i>=1;i--){//从最后一个物体开始算到第一个物体
for(int j=0;j<=C;j++){
if(j>=w[i]) m[i][j]=max(m[i+1][j-w[i]]+v[i],m[i+1][j]);//i+1时的解加上i的重量和价值 与 不加i的（i+1时的解）相比较
else m[i][j]=m[i+1][j];//j<w[i]第i个物体装不下
}
}
return m[1][C];//表格最右上边
}
int main(){
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
cout<<dp();
}
/*
需要求的最大价值
max (v1x1+v2x2+v3x3+......+vixi+vnxn)
需要求的最大价值所占的最大空间
w1x1+w2x2+w3x3+......+wixi+wnxn<=C
xi=0或1 1<=i<=n
定义子问题P（i，W）为：在前i个物品中挑选总重量不超过W的物品，每种物品至多
只能挑选1次，使得总价值最大，此时的最优值记作f（i，W），其中1<=i<=n,1<=W<=C
考虑第i个物品，只有两种可能：选。不选
不选》》》背包容量不变，P（i-1，W）
选》》》 背包容量减小，P（i-1，W-wi）
最优方案就是两个方案哪个更好些
f(i,W)=max{f （i-1，W）,f（i-1，W-wi）+vi}
0 i=0
0 W=0
f （i-1，W） wi>W
f（i-1，W-wi）+vi otherwise
[如果从第一个开始，i=1的话，则i+1，W-w
f(i,j) 表示背包可用容量为j(1<=j<=w),已考虑物品 1,2,3, ... ,i(1<=i<=n) 时的最优解的值。
状态方程：
f(i,j)=f(i-1,j) j<w[i]时，物品i放不下
f(i,j)=max{f(i-1,j) , f(i-1,j-w[i])+v[i]} j>=w[i]时，在放入和不放入物品i之间选最优解
边界条件：
f(i,0)=0 背包不能装入任何物品，总价值为0
f(0,j)=0 没有任何物品装入，总价值为0
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1010;
int n;//n种物体(n<=100)
int C;//背包容积 C(C<=1000)
int v[N],value[N];// 第i(1≤i≤n)件物品的空间和价值。
int f[N];//最优解
int main()
{
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>v[i]>>value[i];
for(int i=1;i<=n;i++)
for(int j=C;v[i]<=j;j--)
f[j]=max(f[j],f[j-v[i]]+value[i]);
cout<<f[C]<<endl;
return 0;
}
*/ 标签：背包,容量,int,max,wi,物品 From： https://www.cnblogs.com/pfwvan666/p/16823437.html