7-13 knapsack problem (10 分)
Given items of different weights and values, we need find the most valuable set of items that fit in a knapsack of fixed capacity . More details: there are a knapsack of capacity c > 0 and n items(c<1000,n<100). Each item has weight wi > 0 and value vi > 0. Find the selection of items (δi = 1 if selected, 0 if not) that fit, sum(δiwi )≤ c, and the total value, sum( δivi), is maximized.
###Input Specifcation:
There are 2 numbers C and n in the first line,that means the capacity and number of items.There are n lines following the first line,there are two numbers in each line,the ith line numbers mean the (i-1)th weight wi-1 > 0and value vi-1 > 0 .
Output Specifcation:
output a number ,it means the max total value.
Input Example:
15 4 3 5 4 6 5 7 7 12
Output Example:
24
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<iostream>
using namespace std;
int n;
int c;
int w[100];
int v[100];
int knapSack(int index,int c){
if(index < 0 || c <= 0)
return 0;
int res=knapSack(index-1,c);
if(w[index]<=c){
res=max(res,knapSack(index-1,c-w[index])+v[index]);
}
return res;
}
int main(){
cin>>c>>n;
for(int i=0;i<n;i++)
cin>>w[i]>>v[i];
cout<<knapSack(n-1,c);
}