动态规划——01背包（仅c++代码）

#include

#include

using namespace std;

int max(int i,int j)

{

?? ?if(i>j) return i;

?? ?else ?return j;

}?

int main()

{

?? ?int v[101];? ? //物品价值

?? ?int w[101];? ??//物品重量

?? ?

?? ?int i;

?? ?

?? ?int m[101][1001];? ? ??//中间数组

?? ?int n,c;? ? ??//? n为物品数量? c为背包大小

?? ?cin>>n>>c;

?? ?for(i=1;i<=n;i++)

?? ?{

?? ??? ?cin>>w[i]>>v[i];

?? ?}

?? ?memset(m,sizeof(m));

?? ?for(i=1;i<=n;i++)

?? ?{

?? ??? ?for(int j=1;j<=c;j++)

?? ??? ?{

?? ??? ??? ?if(j>=w[i])

?? ??? ??? ??? ?m[i][j]=max( m[i-1][j]? ?,? ?m[i-1][? j-w[i]? ] +v[i]? );

? ? ? ? ??

?? ??? ??? ?

?? ??? ??? ?else

?? ??? ??? ??? ?m[i][j]=m[i-1][j];

?? ??? ?}

?? ?}

?? ?

?? ?cout<

?? ?

?? ?return 0;

}

//复制到word，再复制到ide，可以用

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!