P1439 背包九讲(1)：简单的0-1背包
题目描述
有一个箱子容量为 V（正整数，0＜＝V＜＝20000），同时有 n 个物品（0＜n＜＝30），每个物品有一定的体积和价值。要求 n 个物品中，任取若干个装入箱内，在箱子能放得下的前提下，满足箱子内部的价值最大。
输入描述
一个整数 v，表示箱子容量
一个整数 n，表示有 n 个物品
接下来 n 个整数，分别表示这 n 个物品的各自体积和价值
输出描述
一个整数，表示箱子能装下的最大价值。
样例输入
Copy to Clipboard
3
2
2 100
4 200
样例输出
Copy to Clipboard
100
样例解释
输入：
3 // 箱子的总的容量为 3
2 // 一共有两个物品
2 100 // 第一个物品的体积为 2 价值为 100
4 200 // 第二个物品的体积为 4 价值为 200
输出:
100
在箱子能装下的前提下，应该选择第 1 个物品，最大的价值为 100
#include<stdio.h>
#include<vector>
using namespace std;
vector<vector<int>>ps;
void PSet(int n);
void knap(int V[],int value[],int mV);
int main()
{
int wv[31]={0};
int wvalue[31]={0};
int v;int n;
scanf("%d",&v);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&wv[i],&wvalue[i]);
}
PSet(n);
knap(wv,wvalue,v);
return 0;
}
void PSet(int n)
{
vector<vector<int>>psl;
vector<vector<int>>::iterator it;
vector<int>s;
ps.push_back(s);
for(int i=1;i<=n;i++)
{
psl=ps;
for(it=psl.begin();it!=psl.end();++it)
{
(*it).push_back(i);
}
for(it=psl.begin();it!=psl.end();++it)
{
ps.push_back(*it);
}
}
}
void knap(int V[],int value[],int mV)
{
int count =0;
int sumV,sumvalue;
int maxsumV,maxsumvalue=0;
vector<vector<int>>::iterator it;
vector<int>::iterator sit;
for(it=ps.begin();it!=ps.end();++it)
{
sumV=0;sumvalue=0;
for(sit=(*it).begin();sit!=(*it).end();++sit)
{
sumV+=V[*sit-1];
sumvalue+=value[*sit-1];
}
if(sumV<=mV)
{
if(sumvalue>maxsumvalue)
{
maxsumV=sumV;
maxsumvalue=sumvalue;
}
}
}
printf("%d",maxsumvalue);
}
