算法1 Dijkstra算法

时间复杂度为O(n^2)

参考文献

数据结构第二版

C++ 代码

`#include[HTML_REMOVED]
using namespace std;

define MAX 1000

int V,N;
int v[MAX+1],w[MAX+1];
int ans[MAX+1]; //ans[i]表示背包空间为i时的最优解

int main(){
cin>>N>>V;
for(int i=1;i<=N;++i){
cin>>v[i]>>w[i];
}

for(int i=1;i<=V;++i){
    int m=0;
    for(int j=1;j<=N;++j){
        if(i>=v[j])
        m=max(m,ans[i-v[j]]+w[j]); //找出加入的最佳物品种类，可重复添加
    }
    ans[i]=max(m,ans[i-1]);//考虑是否添加
}

cout<<ans[V]<<endl;

}`