算法——动态规划——0_1背包问题
问题描述:
输入:测试样例数,物体的个数,背包的容量,若干物体的价值和体积
输出:背包里最多能容纳的价值
状态转移方程:
表格(初始化见表格):
例:
价值:6 3 5 4 6
重量:2 2 6 5 4
代码:
// DP.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;
void backage0_1(vector<int>value,vector<int>weight,int capacity){ //价值,重量,容量
//vector<int>&goods 选用的物资
//初始化
vector<vector<int> >table(value.size()+1);
for(int i=0;i<=value.size();i++)
table[i].resize(capacity+1);
for(int i=0;i<=capacity;i++)
table[0][i]=0;
for(int i=0;i<=value.size();i++)
table[i][0]=0;
//状态转移
for(int i=1;i<=value.size();i++)
for(int j=1;j<=capacity;j++){
//核心
if(j<weight[i-1])
table[i][j]=table[i-1][j];
else
table[i][j]=max(table[i-1][j],table[i-1][j-weight[i-1]]+value[i-1]);
}
cout<<table[value.size()][capacity]<<endl;
}
int main(){
int times;
cin>>times;
for(int i=0;i<times;i++){
vector<int>value; //价值
vector<int>weight; //重量
int goods_number,capacity; //物体数量,容量
cin>>goods_number;
cin>>capacity;
for(int i=0;i<goods_number;i++){
int tmp; //辅助变量
cin>>tmp;
value.push_back(tmp);
cin>>tmp;
weight.push_back(tmp);
}
backage0_1(value,weight,capacity);
}
return 0;
}