背包最大容量5斤。 总共三件物品。 物品1:重1斤,价值60元 物品2:重2斤,价值100元 物品3:重2斤,价值120元
最主要是要看懂下面这张表:
int main(void) { int goods_num = 3;//总共三件物品 int worth_num = 5;//背包容量最大为5 int goods[] = { 0,60,100,120 };//物品的价值 int weight[] = { 0,1,2,3 };//物品的重量 /*即 物品1 重1斤,价值60人民币*/ vector<vector<int>> vtt; vector<int> vt; for (int i = 0; i <= worth_num; i++)//背包的最大容量 vt.push_back(0); for (int i = 0; i <= goods_num; i++)//物品的价值的个数 vtt.push_back(vt); //该数组 行 为物品的价值 // 列 为背包的重量 for (int i = 1; i <= goods_num; i++)//当前物品的价值 { for (int j = 1; j <= worth_num; j++)//当前背包的重量 { if (j < weight[i])//第i个物品太重,背包中不能承受 { vtt[i][j] = vtt[i - 1][j];//那么,就等于没有该物品前,最大的价值 } else {/*若当前背包可以放下该物品,则有两种选择:放与不放,谁大选谁*/ vtt[i][j] = vtt[i - 1][j] > vtt[i - 1][j - weight[i]]+goods[i] ? vtt[i - 1][j] : vtt[i - 1][j - weight[i]] + goods[i]; } } } cout << vtt[goods_num][worth_num]; return 0; }