Question

用动态规划法解 0/1背包问题要求用c语言编写程序原代码。

实验项目     0/1背包问题1.实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品总价值最大。2.实验要求(1)设计动态规划法的填表过程和求解方法；(3)设计测试数据，并讨论所得结果。

Answer 1

#include <stdio.h>
int main(){
int n,c,cost[50],w[50];
scanf("%d%d",&n,&c);
for (int i=0;i<n;i++)
{
scanf("%d",&cost[i],&w[i]);
}
int dp[100];
for (int j=0;j<n;j++)
for (int i=c;i>=0;i--)
{
if (dp[i]<dp[i-cost[j]]+w[j])
{
dp[i]=dp[i-cost[j]]+w[j];
}
}
printf("%d\n",dp[c]);
return 0;
}