#include<iostream>
using namespace std;
int main(){
//问题:
//有编号分别为1,2,3,4的四件物品,它们的
//重量分别是 3, 7, 2, 1
//它们的价值分别是9,14,10, 4
//每件物品数量只有一个,现在给你个承重为10的背包,
//如何让背包里装入的物品具有最大的价值总和?
//一个存放物品及对应重量和价值的二维数组
//默认生成一个大小为0,价值为0的物品 (但是可以不用赋值,数组默认赋值)
//这个大小和价值为0的物品在后面有大用
int goods[5][2];
//第一个序号——第几个物品
//第二个序号——0是重量 1是价值
goods[1][0]=3;
goods[1][1]=9;
goods[2][0]=7;
goods[2][1]=14;
goods[3][0]=2;
goods[3][1]=10;
goods[4][0]=1;
goods[4][1]=4;
//创建一个大数组,存放后面的数据
int arr[5][11];
//数组——列长为:5 行宽为:11
//0~10对应当前背包大小
//0~4 对应当前物品序号
//效果如下:
//\ 0 1 2 3 4 5 6 7 8 9 10
//0
//1
//2
//3
//4
//现在给行列序号为0的先赋值为0
//(也可以不做这步,这里只是方便理解)
for(int i=0;i<11;i++){
arr[0][i]=0;
arr[i][0]=0;
}
//效果如下:
//\ 0 1 2 3 4 5 6 7 8 9 10
//0 0 0 0 0 0 0 0 0 0 0 0
//1 0
//2 0
//3 0
//4 0
//从左到右从,从上到下,一排一排扫描判断
//下面是对if判断语句的解释:
//if(当前背包容量j < 当前待加入物品重量good[i][0]){
//则当前位置对应最大价值arr[i][j] = 它头顶位置对应的最大价值arr[i-1][j]}
// if(当前背包容量j >= 当前待加入物品重量good[i][0]){
// { 当前位置对应最大价值 = (判断下面1,2哪个更大);
//1.它头顶位置对应的最大价值arr[i-1][j] ,
//2.(比它头上位置"对应的背包容量"arr[i-1][j] 小 当前位置对应物品重量goods[i][0] 的位置的价值 加上当前物品价值goods[i][1])
//(arr[i-1][j-goods[i][0]]+goods[i][1])
for(int i=1;i<=4;i++){
for(int j=1;j<=10;j++){
if(j<goods[i][0]){
arr[i][j]=arr[i-1][j];
}
if(j>=goods[i][0]){
if(arr[i-1][j]>(arr[i-1][j-goods[i][0]]+goods[i][1])){
arr[i][j]=arr[i-1][j];
}else{
arr[i][j]=(arr[i-1][j-goods[i][0]]+goods[i][1]);
}
}
}
}
for(int i=0;i<5;i++){
for(int j=0;j<11;j++){
cout<<arr[i][j]<<"\t";
}
cout<<endl;
}
//最后:
//0 0 0 0 0 0 0 0 0 0 0
//0 0 0 9 9 9 9 9 9 9 9
//0 0 0 9 9 9 9 14 14 14 23
//0 0 10 10 10 19 19 19 19 24 24
//0 4 10 14 14 19 23 23 23 24 28
//从上面可以看出 当背包容量大小为10的时候,最大价值为28
}