编辑代码

//knapsack.cpp : 定义控制台应用程序的入口点
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
/*
	0-1 背包问题（迭代版）
	输入：
		products_count：商品的数量
		capacity：背包的容量
		weight_array：商品重量数组
		value_array：商品价格数组
		result：结果数组
*/
 
int knapsack(int products_count,int capacity,vector<int> &weights,vector<int> &values,vector<vector<int>> &res){
	for(int i=1;i<=products_count;i++){//i个物品 
		for(int j=1;j<=capacity;j++){//背包容量为j 
			if(weights[i] > j){//当前背包的容量 j 放不下第 i 件商品时
			    res[i][j] = res[i-1][j];
			}else
			{
				res[i][j] = max( res[i-1][j-weights[i]] + values[i] , res[i-1][j]);
			}
		}		
	}
		
	return res[products_count][capacity];
}
 
int main(){
	int products_count,capacity;
	cout << "please input products count and knapsack's capacity: " << endl; // 输入商品数量和背包容量
	cin>>products_count>>capacity;
	vector<int> weights(products_count + 1,0);
	vector<int> values(products_count + 1,0);
	cout << "please input weight array for " << products_count << " products" << endl;
	for(int i=1;i<=products_count;i++)
		cin>>weights[i];
 
	cout << "please input value array for " << products_count << " products" << endl;
	for(int i=1;i<=products_count;i++)
		cin>>values[i];
		
	vector<vector<int>> res(products_count + 1,vector<int> (capacity + 1,0));
	knapsack(products_count,capacity,weights,values,res);
	cout << "knapsack result is " << res[products_count][capacity] << endl;
 
		
	return 0;
}