Question

一道C语言题目：网上找到的大多数都是有错误的，哪个高手能整个没错的给我？

假设有n件物品，这些物品的重量分别是W1 , W2 , … , Wn，物品的价值分别是V1，V2， …，Vn。求从这n件物品中选取一部分物品的方案，使得所选中的物品的总重量不超过限定的重量W（W<∑Wi, i=1,2,┅,n），但所选中的物品价值之和为最大。

Answer 1

#include<stdio.h>
int w[1000],v[1000];
int dp[100000]={0};
int main()
{
int n,m;
int i,j;
puts("输入物品个数N和限定重量W：");
scanf("%d%d",&n,&m);
puts("输入N个物品的重量");
for(i=0;i<n;i++)scanf("%d",&w[i]);
puts("输入N个物品的价值");
for(i=0;i<n;i++)scanf("%d",&v[i]);
for(i=0;i<n;i++)
{
for(j=m;j>=w[i];j--)
{
if(dp[j-w[i]]+v[i]>dp[j])
dp[j]=dp[j-w[i]]+v[i];
}
}
printf("%d\n",dp[m]);
return 0;
}

Answer 2

这个是一个0-1动态规划的问题，给你个网址，你去看看http://wenku.baidu.com/view/7ce09508f12d2af90242e621.html
然后你就可以看懂
for(i=0;i<n;i++)
{
for(j=m;j>=w[i];j--)
{
if(dp[j-w[i]]+v[i]>dp[j])
dp[j]=dp[j-w[i]]+v[i];
}
}

这个是怎么回事了

Answer 3

给分我就给你写，重量和价值是给定的还是需要输入的

追问

好，分数没问题！重量和价值都是要输入的！