or
1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式
s[i][j]=
s[i-1][j],
wi>j
max{s[i-1][j],s[i-1][j-wi]+vi},
wi<=j
s[0][j]=0
1<=j<=W
s[i][0]=0
1<=i<=n
所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。
以上的W是只考虑整数的。
你这是完全背包。01背包每个物品只能装一次，因此必须和上一个物品比较，否则会出现重复装的情况。
f[i][j]表示把前i个物品装入容量为j的箱子能得到的最大价值则有：
f[i][j]=max(f[i-1][j]/*不装*/,f[i-1][j-c]+v/*装，但必须满足j>=c*/)
改好的代码如下所示：
#include <algorithm>#include <iostream>
#include <string.h>
using namespace std
int main(int argc, char *argv[])
{
int c[] = {0,5,3,4,3,5}//消耗
int v[] = {0,500,200,300,350,400} // value
int f[6][11]
memset(f,0,sizeof(f)) //归位0
for(int i = 1 i <= (sizeof(c)/sizeof(int) - 1) i++) //i 第几个物品
{
for(int p = 1 p <= 10 p++) //表示10 个空间
{
if(p < c[i])
{
f[i][p] = f[i][p - 1]
}
else
{
// f[i][p] = max(f[i - 1][p], f[i][p - c[i]] + v[i])
f[i][p] = max(f[i - 1][p], f[i - 1][p - c[i]] + v[i])
}
}
}
printf("%d",f[5][10])
return 0
}
这是一个背包问题，该算法已经是最简单的了，还有递归算法，我觉得更麻烦。对你的代码进行解释如下：
//背包问题：有m件物品和一个承重为t的背包。第i件物品的重量是w[i]，价值是v[i]。//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include <stdio.h>
#include <conio.h>
#include <string.h>
int f[1010],w[1010],v[1010]//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
int max(int x,int y){//返回x,y的最大值
if(x>y) return x
return y
}
int main(){
int t,m,i,j
memset(f,0,sizeof(f)) //总价值初始化为0
scanf("%d %d",&t,&m) //输入背包承重量t、物品的数目m
for(i=1i<=mi++)
scanf("%d %d",&w[i],&v[i]) //输入m组物品的重量w[i]和价值v[i]
for(i=1i<=mi++){ //尝试放置每一个物品
for(j=tj>=w[i]j--){
f[j]=max(f[j-w[i]]+v[i],f[j])
//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
}
}
printf("%d",f[t]) //输出承重量为t的背包的总价值
printf("\n")
getch()
return 0
}
