假设有n件物品，每件物品都有各自的重量和价值，现在给一个最多可以装v重量的背包，请问如何装才能使价值最大。
用动态规划，状态转移方程是:
v[i][j]=max(v[i-1][j], v[i-1][j-goods[i-1].weight] + goods[i-1].value)
v是一个二维数组，行代表第几件物品，列代表背包容量，第一行和第一列的所有值都是0。v[i][j]代表第i件物品，在volumn是j的时候，可以放的最大价值。
goods[i-1]，代表的是goods数组里的第i件物品，因为下标是从0开始的。
#include <iostream>
using namespace std;
const int N = 10;
struct goods{
int idx;
int weight;
int value;
};
//struct good goods[N];
struct goods goodss[5] = {{1,2,6},
{2,2,3},
{3,6,5},
{4,5,4},
{5,4,6}};
int KnapSack(int n,struct goods goodss[],int volumn){
int V[N][10*N]; //初始化10行100列的数组
for(int i = 0; i <= n; i++)//初始化第0列
V[i][0] = 0;
for(int j = 0; j <= volumn; j++)//初始化第0行
V[0][j] = 0;
for(int j = 0; j <= volumn; j++)
cout<<V[0][j]<<" ";
cout<<endl;
for(int i = 1; i <= n; i++) // 迭代物品
{
for(int j = 1; j <= volumn; j++) // 对于每个重量进行处理
if(j < goodss[i-1].weight)
V[i][j] = V[i-1][j]; // 当前物品的重量大于背包重量，用前一个物品的当前volumn的结果
else
V[i][j] = max(V[i-1][j],V[i-1][j-goodss[i-1].weight] + goodss[i-1].value); //当前goods的下标是[i-1]
for(int j = 0; j <= volumn; j++)
cout<<V[i][j]<<" ";
cout<<endl;
}
return V[n][volumn];
}
int main()
{
int n=5;
int volumn=10;
int sum = KnapSack(n,goodss,volumn);
cout<<"sum is "<<sum<<endl;
return 1;
}
leetcode上的coin change，要求的是用最少的硬币，组成一个特定值
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
经典的动态规划题
注意点： 一开始先初始化一维数组的内容为比总额大1，同时大小是总额+1，因为数组下标是从0开始，要使数组最后一个元素是总额，总大小是总额+1
m*n的时间复杂度
只有 coin <= i: 才能做方程
class Solution(object):
def coinChange(self, coins, amount):
"""
Very classic dynamic programming problem, like 0-1 Knapsack problem.
dp[i] is the fewest number of coins making up amount i,
then for every coin in coins, dp[i] = min(dp[i - coin] + 1).
"""
dp = [amount + 1] * (amount + 1) # construct a list with (amount+1) elements, each element value is (amount+1)
dp[0] = 0
#for i in range(amount + 1):
for coin in coins:
for i in range(1, amount + 1):
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[amount] > amount else dp[amount]
对于{2,3,5}的coin，总价值是10，输出矩阵应该是：
0 0 1 2 3 4 5 6 7 8 9 10
2 0, 11, 1, 11, 2, 11, 3, 11, 4, 11, 5
3 0, 11, 1, 1, 2, 2, 2, 3, 3, 3, 4
5 0, 11, 1, 1, 2, 1, 2, 2, 2, 3, 2
网友评论