给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为c(c<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每

### 回答1：
个物品只有装入或不装入两种情况，不能将物品分割成小块装入，也不能重复装入。可以使用动态规划算法来解决这个问题。

具体步骤如下：

1. 定义状态：设f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。

2. 状态转移方程：对于第i个物品，有两种情况：

(1) 不放入背包中，此时f[i][j]=f[i-1][j]；

(2) 放入背包中，此时f[i][j]=f[i-1][j-wi]+vi。

综合两种情况，得到状态转移方程：f[i][j]=max{f[i-1][j], f[i-1][j-wi]+vi}。

3. 边界条件：f[][j]=，f[i][]=。

4. 最终结果：f[n][c]即为所求的最大价值。

5. 时间复杂度：O(nc)。

因此，可以使用动态规划算法来解决背包问题，找到最优解。

### 回答2：
个物品，只有选择或者不选择两种情况，因此可以使用动态规划来解决这个问题。

设dp[i][j]表示将前i个物品装入容量为j的背包中所得到的最大价值，那么：

当不选择第i个物品时，dp[i][j] = dp[i-1][j]；

当选择第i个物品时，dp[i][j] = dp[i-1][j-wi] + vi；

综上，将第i件物品放入背包中时，若能够放入，则需要比较不放入该物品所得到的价值与放入该物品的总价值，取较大值；若不能够放入，则最大价值不变，即dp[i][j] = dp[i-1][j]。

最后的结果为dp[n][c]。

具体实现中，可以使用一维数组来保存动态规划的结果，每次从后往前更新数组，防止重复计算。

代码如下：

int dp[MAX_C+1] = {0};
for(int i=1; i<=n; i++) {
for(int j=c; j>=w[i]; j--) {
dp[j] = max(dp[j], dp[j-wi] + vi);
}
}
return dp[c];

### 回答3：
个物品，可以选择将其完全装入背包，也可以选择将其部分装入背包，即装入一部分的重量。但是，装入的物品的总重量不能超过背包的容量，即∑wi<=c。

背包问题是一种经典的动态规划问题，可以用动态规划算法来解决。动态规划算法的核心思想是将大问题分解成小问题来解决。

我们可以定义状态dp[i][j]表示将前i个物品装入容量为j的背包中所能获得的最大价值。则dp[i][j]有两种情况：

1. 不将第i个物品装入背包中，则有dp[i][j]=dp[i-1][j]。

2. 将第i个物品装入背包中，则有dp[i][j]=dp[i-1][j-wi]+vi。

综上所述，dp[i][j]的值为这两种情况中的最大值。最终的答案即为dp[n][c]。

下面是具体的动态规划算法：

1. 初始化dp数组，令dp[i][0]=0，dp[0][j]=0。

2. 对于每个物品i和容量j，计算dp[i][j]的值：

如果wi>j，则dp[i][j]=dp[i-1][j]；

否则，dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi)。

3. 最终答案为dp[n][c]。

算法复杂度为O(nc)，其中n为物品的种数，c为背包的容量。

此外，还可以用贪心算法来解决背包问题。具体思想是将物品按照单位重量价值（vi/wi）从大到小排序，然后将价值最大的物品先装入背包中。如果背包还有剩余空间，则继续选择下一个单位重量价值最大的物品，直到背包填满为止。贪心算法的时间复杂度为O(nlogn)。但是，对于某些特殊情况，贪心算法可能无法得到最优解。