Question

给定n种物品和一个背包,物品I的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使

给定n种物品和一个背包,物品I的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使

Answer 1

给定一个背包和n个物品，其中第i个物品的重量为Wi，价值为Vi，试求解如何选择装入背包的物品，使得背包中物品的价值最大。使用动态规划算法列出相应的目标函数、约束方程和子问题递推方程，伪代码，并使用一种语言进行编程实现。
是这个不？？？？？？？

Answer 2

#include<iostream>
using namespace std;
int w[1000],v[100];
int f[105][1005];
int x[100];
int main(){
int T,M,i,j;
while( cin>>M>>T){
for( i=1;i<=M;i++){
cin>>w[i]>>v[i];
}
for( i=1;i<=M;i++){
for(j=0;j<T;j++){
if(j>=w[i]){
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
else
f[i][j]=f[i-1][j];
}

}

for(i=1;i<=M;i++){
for(j=T;j>=w[i];j--){

x[j]=max(x[j],x[j-w[i]]+v[i]);
// cout<<x[T]<<" "<<j<<endl;
}
}

//cout<<x[T]<<" "<<j<<endl;
// for(i=0;i<=M;i++){
// cout<<f[i][T-1]<<endl;
//
// }
cout<<f[M][T-1]<<endl;}

return 0;
}

Answer 3

朋友，请问你想问什么？